백준 1303번 전투 | python | bfs

문제

링크

풀이

이코테의 음료수 얼려먹기 문제랑 거의 동일한 문제이다.

문제의 포인트는 일단 우리 병사와 적국 병사의 그룹, 그리고 각 그룹의 인원수를 파악해야 하는 것인데 이는 bfs로 쉽게 구할 수 있다. (물론 dfs로도 풀이 가능)

bfs 동작 과정은 아래와 같으며, 아직 bfs와 dfs 개념 자체가 선명하지 않다면 이 포스팅을 읽어보고 오는 것을 추천한다.

bfs 동작 과정

1. 맵의 왼쪽 상단 좌표부터 차례로 bfs를 돌린다. 이 때 현재 좌표를 먼저 큐에 삽입함과 동시에 현재 좌표에 있는 병사가 적군인지 아군인지 확인하여( = arr[y][x] ) cur 변수에 저장한다.
2. while문을 통해 큐가 빌 때까지 아래의 과정을 반복한다.
3. pop을 통해 현재 좌표를 불러오고, 카운트를 센다 (= cnt+=1 )
4. 현재 좌표로부터 인접한 상하좌우를 탐색한다.
   • 이 때 상하좌우의 좌표가 범위 내에 있는지, 방문하지 않은 좌표인지, 마지막으로 현재 위치에 있는 병사와 같은 팀의 병사인 지 확인한다.
5. 4의 조건에 부합하다면 큐에 해당 인접 좌표를 삽입한다. (해당 좌표를 다시 현재 좌표로 설정하여 3~4를 반복하기 위함) 또한 방금 넣은 좌표의 방문 여부를 표시하기 위해 해당 arr의 값을 1로 설정한다.
6. bfs() 실행이 종료되면 그룹 하나를 확인했다는 것이므로 그룹 내 인원을 파악할 수 있는 변수인 cnt를 반환한다.

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())


arr = []
for _ in range(m):
    arr.append(list(input().strip()))

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(y, x):
    q = deque()
    q.append((y, x))
    cur = arr[y][x]
    arr[y][x] = 1  # 방문했음을 의미
    cnt = 0  # 시작 ~!
    while q:
        y, x = q.popleft()
        cnt += 1
        for dy, dx in d:
            Y, X = y + dy, x + dx
            if (0 <= X < n) and (0 <= Y < m) and arr[Y][X] == cur:
                q.append((Y, X))
                arr[Y][X] = 1
    return cnt


w_cnt = 0
b_cnt = 0

for i in range(m):
    for j in range(n):
    	# bfs()로 반환된 cnt는 적군, 아군에 따라 따로 위력을 계산해준다.
        if arr[i][j] == "W":
            w_cnt += bfs(i, j) ** 2
        elif arr[i][j] == "B":
            b_cnt += bfs(i, j) ** 2


print(w_cnt)
print(b_cnt)

🦾 깨달은 점

1. 상하좌우는 튜플을 리스트에 저장해두는 방식으로 입력 하는 것이 개인적으로 편하다
   • d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   • for dy, dx in d
   • Y = dy+y
   • X = dx+x
2. y는 행, x는 열로 생각해서 풀 것. 괜히 인덱스 에러로 고생하지 말자
3. bfs()로만 풀다보니까 dfs() 재귀 방식으로 풀이하는 데 거부감이 쌓이는 것 같다. bfs()는 큐의 삽입/삭제 과정이 추가되므로 엄밀히 따지면 dfs()가 시간 면에서 더 우수하므로 dfs()가 조금 더 유리할 수 있다. 편식하지 말자
4. 방문 여부는 다양하게 저장할 수 있다
   • 위 풀이에서는 arr에 등장하지 않던 숫자 1로 초기화해줌으로써 방문여부를 파악했다. 보통 visited 배열을 따로 두고 방문 여부를 확인할 수도 있는데 위 방식대로 하면 별도의 배열이 필요하지 않게되므로 메모리를 줄일 수 있다는 이점이 있다.
   • 하지만 헷갈린다면 별도의 visited 배열을 꼭 두어 사용하자
   • 방문 여부 확인과 동시에 값을 갱신해야하는 경우도 생길 수 있다. visited(또는 check라고도 많이 이름을 짓는다) 라고 해서 '방문'에만 초점을 맞추지 말고 다양한 조건이 붙을 수 있음을 유의하자