[1303] - 전쟁 - 전투

1303번 - 전쟁 - 전투

이번 문제에서는 BFS 라는 알고리즘을 살짝 알아둘 필요가 있다.

BFS란, 너비 우선 탐색이라고 불리우는 탐색 방식으로.. 가까이 있는 데이터를 우선적으로 탐색하는 것으로 이해하면 된다.

해당 문제에서는 전쟁에 위력을 인접한 사람수의 제곱이기 때문에 인접한 사람수만 잘 구하면, 해당 값의 제곱합으로 답을 도출할 수 있다.

인접한 사람이라는 기준은 해당 사람에서 동서남북(대각선 제외)임으로 현재 위치에서 각각 동서남북 먼저 탐색하면된다. 탐색할 때 주의점은 이전에 방문 곳은 visited로 체크해서 다시 가지 않는 것이고, 탐색했을 때 같은 병사인 경우에만 방문을 한다는 것이다.

즉, visited = 1(또는 Ture)가 아니고, 현재 병사와 방문할 병사의 값이 일치한 경우에만 방문한다.

입력 받기

    W_COUNT = 0
    B_COUNT = 0
    M, N = map(int, input().split())
    fields = []
    visited = [[0]*M for _ in range(N)]
    for i in range(N):
        fields.append(str(input()))

W_COUNT 를 우리 병사, 적국은 B_COUNT에 값을 저장하기로 하고, 각각 값을 받는다. visited는 각 병사들을 탐색했는지(방문했는지) 여부를 저장하기 위해 0으로 초기화 시킨다.

탐색하기

W, B 우리편과 적군이 필드에 듬성듬성 있을 수 있다. 탐색할때 시작점을 정하기 위해서..

방문하지 않은 것(if visited[i][j] != 1:)인 경우 탐색을 시작한다.

    for i in range(N):
    for j in range(M):
        if visited[i][j] != 1:
            c = bfs(fields, i, j, visited)
            # print(i, j, c**2)
            if fields[i][j] == 'W':
                W_COUNT += (c**2)
            else:
                B_COUNT += (c**2)

해당 i,j에서 탐색을 시작하면,

c = bfs(fields, i, j, visited) 를 통해서 BFS 탐색을 진행하는데…

def bfs(graph, sx, sy, visited):
    movex = [0, 0, -1, 1]
    movey = [-1, 1, 0, 0]
    queue = deque()
    queue.append((sx, sy))
    visited[sx][sy] = 1
    count = 1
    while queue:
        vx, vy = queue.popleft()
        for i in range(4):
            tx = vx+movex[i]
            ty = vy+movey[i]
            if N > tx >= 0 and M > ty >= 0 and visited[tx][ty] != 1:
                if graph[vx][vy] == graph[tx][ty]:
                    count += 1
                    queue.append((tx, ty))
                    visited[tx][ty] = 1
    return count

해당 메소드에서 동서남북으로 움직이기 위해 x,y좌표로 각각 움직이는 것을 리스트로 지정한다.

해당 리스트에서 0 번째는 (x:0, y:-1), 1 번째는 (0,1), 2 번째는 (-1,0) 이런식으로 된다.

우선 시작 점의 x, y를 큐안에 넣는다.

queue = deque()
queue.append((sx, sy))
visited[sx][sy] = 1

풀이

from collections import deque
import queue

def bfs(graph, sx, sy, visited):
    movex = [0, 0, -1, 1]
    movey = [-1, 1, 0, 0]
    queue = deque()
    queue.append((sx, sy))
    visited[sx][sy] = 1
    count = 1
    while queue:
        vx, vy = queue.popleft()
        for i in range(4):
            tx = vx+movex[i]
            ty = vy+movey[i]
            if N > tx >= 0 and M > ty >= 0 and visited[tx][ty] != 1:
                if graph[vx][vy] == graph[tx][ty]:
                    count += 1
                    queue.append((tx, ty))
                    visited[tx][ty] = 1
    return count

if __name__ == '__main__':
    W_COUNT = 0
    B_COUNT = 0
    M, N = map(int, input().split())
    fields = []
    visited = [[0]*M for _ in range(N)]
    for i in range(N):
        fields.append(str(input()))

    for i in range(N):
        for j in range(M):
            if visited[i][j] != 1:
                c = bfs(fields, i, j, visited)
                # print(i, j, c**2)
                if fields[i][j] == 'W':
                    W_COUNT += (c**2)
                else:
                    B_COUNT += (c**2)

    print(W_COUNT)
    print(B_COUNT)