[백준/bfs] 1303번: 전쟁-전투

-문제:https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

풀이 없이 스스로 푼 문제. Silver Level1 문제이다. 탐색에는 특히 골드 문제가 많기 때문에 계속해서 탐색공부를 해야할 것 같다 

주의해야할 점이 세로가 m, 가로가 n이기 때문에 이것을 고려해서 풀어야한다

-정답풀이: 

처음에는 dfs로 풀었는데 틀려서 bfs로 바꿔서 풀고 맞힌 문제이다 

from collections import deque

def bfs(x,y,word):
    visit[x][y]=1
    cnt=1
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if not visit[nx][ny] and s[nx][ny]==word:
                    visit[nx][ny]=1
                    cnt+=1
                    q.append((nx,ny))
    return cnt

n,m=map(int,input().split()) 
s=[list(input()) for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*n for _ in range(m)]
white=0
blue=0

for i in range(m):
    for j in range(n):
        if not visit[i][j]:
            if s[i][j]=='W':
                ans=bfs(i,j,'W')
                white+=(ans**2)               
            elif s[i][j]=='B':
                ans=bfs(i,j,'B')
                blue+=(ans**2)
                
print(white,blue)