[ 파이썬(python) ] 백준 1303 - 전쟁 - 전투(BFS)

📌 백준 1303 - 전쟁 - 전투

문제 설명

---

💡 나의 풀이

(여담이지만 1303 하니까 국방 헬프콜이 생각났다.)

 

2차원 배열에서 각 색깔에 맞는 거리를 구하는 전형적인 BFS문제이지만, 헷갈린 부분들이 많았다. 한쪽 BFS만 구하는것이 아니고 양쪽 BFS를 모두 구현해야하다보니까 함수를 어떻게 선언하는지 굉장히 고민을 많이 했다.

결론적으로 BFS 함수에 color라는 파라미터를 작성해서 넘겨줬고 함수내에서 각 칸의 거리를 구하는 방법은 각 색깔별로 w_cnt, b_cnt를 따로따로 선언하지 않고 cnt 변수 하나만 선언해서 색깔 별로 조건문을 다르게 주어 현재 들어온 색을 기준으로 cnt를 세고 return하는 방법으로 진행했다.

 

이 방법까지 캐치하는데 상당히 오랜 시간이 걸렸다. 어제 첫 알고리즘 문제로 선정했으나, 당시에는 풀지 못했고 이후 완벽하게 구현 방법을 머릿속에 넣고 싶어 오늘 21시까지 미뤄뒀다가 다시 풀었다.

 

BFS의 구현방법을 알더라도 문제의 유형에 따라서 입력값을 다르게 줘야 하는 경우가 생기는데 지금까지 내가 풀었던 유형은 다음과 같다.

1. 정석적인 BFS 구현: boj_1260 - DFS와 BFS
2. 각각의 기준점 별 거리계산: boj_2667 - 단지번호붙이기, boj_1303 - 전쟁 - 전투
3. 시작 지점이 2곳 이상인 좌표를 동시에 BFS 구현: boj_7576 - 토마토
4. 한 기준점이 다른 기준점에 영향을 미치는 BFS: boj_4179 - 불!
5. 범위별 최대 BFS 구하기: boj_2468 - 안전 영역
6. 등등...

728x90

많이 풀지는 못했지만 어떤 문제는 풀었던 문제 같고 반대로 어떤 비슷한 문제는 방법을 완전히 다르게 해야 하는 경우도 많았다. 흐름을 아는 것이 중요한 것 같다. 그리고 BFS 관련된 문제가 엄청많았다. 척 보면 이런 유형이구나를 알 때까지 풀어야겠다는 생각이 들었다.

풀이 방법을 살펴보자.

 

1. 방문 기록이 없고 현재 값이 W인 값 혹은 방문기록이 없고 현재 값이 B인 값을 함수로 넣어준다.
2. color별로 cnt를 증가시킨다.
3. return cnt+1 한 값에 제곱해주고 색깔별로 누적시킨다.

 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y, color):
    cnt = 0
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] == color and not visited[nx][ny]:    # each color check
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    cnt += 1    # each color count

    return cnt + 1

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
graph = [list(input()) for _ in range(m)]
visited = [[False] * n for i in range(m)]

white, blue = 0, 0
for i in range(m):
    for j in range(n):
        if graph[i][j] == 'W' and not visited[i][j]:
            white += bfs(i, j, 'W') ** 2    # count accumulate
        elif graph[i][j] == 'B' and not visited[i][j] :
            blue += bfs(i, j, 'B') ** 2    # count accumulate

print(white, blue)