BOJ [Silver I] 전쟁 - 전투 - 1303 (BFS 풀이)

문제 링크

DFS 풀이

내 코드: 틀렸습니다

from collections import deque

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w, b = 0, 0

def bfs(x, y):
    global w, b
    if graph[x][y] == 'W':
        q_w = deque([(x, y)])
        cnt = 0
        while q_w:
            x, y = q_w.popleft()
            graph[x][y] = 'X'
            for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                nx, ny = x+dx, y+dy
                if 0<=nx<m and 0<=ny<n and graph[nx][ny] == 'W':
                    q_w.append((nx, ny))
                    cnt += 1
        w += cnt ** 2

    elif graph[x][y] == 'B':
        q_b = deque([(x, y)])
        cnt = 0
        while q_b:
            x, y = q_b.popleft()
            graph[x][y] = 'X'
            for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                nx, ny = x+dx, y+dy
                if 0<=nx<m and 0<=ny<n and graph[nx][ny] == 'B':
                    q_b.append((nx, ny))
                    cnt += 1
        b += cnt ** 2
    return
    
                    
for i in range(m):
    for j in range(n):
        bfs(i, j)

print(w, b)

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW
출력: 170 100
정답: 130 65

• 'W' 보면 $11^2$ + $7^2$ 으로 나옴

• 이유: 몰라요 더 공부하겠슴니다..

다른 사람 코드 참고

from collections import deque

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w, b = 0, 0


def bfs(x, y, team):
    q = deque([(x, y)])
    cnt = 0
    while q:
        x, y = q.popleft()
        
        for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            nx, ny = x+dx, y+dy
            if 0<=nx<m and 0<=ny<n and graph[nx][ny] == team:
                q.append((nx, ny))
                cnt += 1
                graph[nx][ny] = 'X'
    return cnt if cnt != 0 else 1
    
    
for i in range(m):
    for j in range(n):
        team = graph[i][j]
        if team == 'W':
            w += bfs(i, j, team) ** 2
        elif team == 'B':
            b += bfs(i, j, team) ** 2

print(w, b)

• graph[nx][ny] = 'X' 를 for문 앞에(x, y pop 한 다음 빈 줄에) 넣으면 170 101 나오고 범위 체크할 때 같이 넣어주면 정답 나옴

• 그냥 일단 dfs bfs를 다시 공부해야 할 듯 이해가 되면 수정하러 오겠어요~ㅠ