[백준] 1303 - 전쟁-전투 (Python)

[백준] 1303 - 전쟁-전투

• https://www.acmicpc.net/problem/1303
• 알고리즘:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
  • 깊이 우선 탐색

풀이1 - BFS

import sys

N,M=map(int, input().split())
arr=[list(sys.stdin.readline().strip()) for _ in range(M)]
visited=[[0]*(N) for _ in range(M)]

dx=[-1,1,0,0] #상,하,좌,우
dy=[0,0,-1,1] #상,하,좌,우

sum_w=sum_b=0

def bfs(x,y,T):
    num=0
    queue=[(x,y)]
    visited[x][y]=1
    while queue:
        num += 1
        x=queue[0][0]
        y=queue[0][1]
        queue.pop(0)
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N:
                if arr[nx][ny]==T and visited[nx][ny]==0:
                    visited[nx][ny]=1
                    queue.append((nx,ny))
    return num

for i in range(M):
    for j in range(N):
        if arr[i][j]=='W' and visited[i][j]==0:
            sum_w+=bfs(i,j,'W')**2
        elif arr[i][j]=='B' and visited[i][j]==0:
            sum_b+=bfs(i,j,'B')**2

print(sum_w,sum_b)

📌 반복문으로 여러줄을 입력 받을 때 input()으로 입력받는 경우 시간초과가 발생할 수 있으므로, sys.stdin.readline()을 사용하였다.

• algorithms