[Python] 백준 #1303번 - 전쟁 - 전투

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

내 코드

import sys
from collections import deque

def bfs(graph,visited,start):
    queue = deque([start])
    visited[start] = True
    
    cnt=0

    while queue:
        v = queue.popleft()
        cnt+=1
        for i in graph[v]:
            if visited[i] == False:
                visited[i] = True
                queue.append(i)
    return cnt

N,K = map(int,input().split())
arr=[]
for i in range(K):
    tmp=[]
    for color in sys.stdin.readline()[:-1]:
        tmp.append(color)
    arr.append(tmp)


graph = [[] for _ in range(K*N)]
visited = [False for _ in range(K*N)]

cnt=0
for i in range(K):
    cnt=i*N
    for j in range(N-1):
        if arr[i][j] == arr[i][j+1]:
            graph[cnt].append(cnt+1)
            graph[cnt+1].append(cnt)
        cnt+=1

cnt=0
for i in range(K-1):
    cnt=i*N
    for j in range(N):
        if arr[i][j] == arr[i+1][j]:
            graph[cnt].append(cnt+N)
            graph[cnt+N].append(cnt)
        cnt+=1

scoreW,scoreB = 0,0

for i in range(K*N):
    if visited[i] == False:
        score = bfs(graph,visited,i)
        if arr[i//N][i%N] == 'W':
            scoreW+=score**2
        else:
            scoreB+=score**2

print(scoreW,scoreB)

너비우선탐색(bfs)로 풀었다.

먼저 입력받은 문자열들을 0~K*N(미포함)까지 그래프로 만들어주었다. 이때 위,아래, 양 옆이 같은 단어일때만 그래프에 추가해주었다. 그리고 이 그래프를 이용해서 너비우선탐색을 한다.

K*N까지 반복문을 실행하면서 방문하지 않았던 노드에 방문한다. 이때 그 시작 노드의(i) W,B를 체크하였다.

bfs를 수행하면서 노드를 몇개 방문했는지 검사하여 스코어를 계산해준다.

 

 

다른사람 코드

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)

bfs로 푼 방법이다. dx,dy를 사용하여 기준점의 상하좌우를 구한다.

상하좌우의 좌표가 범위 내에 있을때 그 좌표의 색이 처음에 넘겨준 색과 같고 방문하지 않았을 경우 그 좌표를 방문해준다. 그리고 큐에 좌표를 더해주고 cnt를 더해준다.