1303번: 전쟁 - 전투

 

 

 

풀이

 

dfs 와 bfs로 풀 수 있는 문제입니다.

 

 

dfs

...

아직 방문하지 않은 visited[i][j]가 == 'W' or 'B'인곳에서 dfs을 호출하고 visited[x][y] = 'V' 로 방문처리 해줍니다.

 

visited[i][j]가 'W', 'B'중 하나에 해당한다면 해당값으로 change의 값을 바꿔줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 visited[nx][ny] == change 라면 dfs를 재호출 하고 cnt의 값을 1 증가시킵니다.

 

주위에 같은색 병사가 없다면 병사들이 뭉쳐있는 구역을 다 탐색한것이므로 cnt^2 을한 결과를 result에 할당합니다. 

...

 

 

 

bfs

...

아직 방문하지 않은 visited[i][j]가 == 'W' or 'B'인곳에서 bfs을 호출하고 visited[x][y] = 'V' 로 방문처리 해줍니다.

 

visited[i][j]가 'W', 'B'중 하나에 해당한다면 해당값으로 change의 값을 바꿔줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 visited[nx][ny] == change 라면 방문처리를하고 queue에 nx,ny를 삽입한뒤 cnt의 값을 1 증가시킵니다.

 

주위에 같은색 병사가 없다면 병사들이 뭉쳐있는 구역을 다 탐색한것이므로 cnt^2 을한 결과를 result에 할당합니다. 

...

 

 

파이썬 dfs

import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global cnt
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    visited[x][y] = 'V'

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i] 

        if 0 <= nx < m and  0 <= ny < n and visited[nx][ny] == change:
            dfs(nx, ny)
            cnt += 1

n, m = map(int, input().split())
graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(m)]
visited = [item[:] for item in graph]

cnt = 1
result1 = 0
result2 = 0
change = ""

for i in range(m):
    for j in range(n):
        if visited[i][j] == 'W':
            change = 'W'
            dfs(i, j)
            result1 += cnt * cnt    
            cnt = 1

visited = [item[:] for item in graph]
for i in range(m):
    for j in range(n):
        if visited[i][j] == 'B':
            change = 'B'
            dfs(i, j)
            result2 += cnt * cnt    
            cnt = 1

print(result1, result2)

 

 

 

파이썬 bfs

from collections import deque
import sys

def bfs(x, y):
    global cnt
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    visited[x][y] = 'V'

    queue = deque()
    queue.append((x, y))
    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 and visited[nx][ny] == change:               
                visited[nx][ny] = 'V'
                queue.append((nx, ny))
                cnt += 1

n, m = map(int, input().split())
graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(m)]
visited = [item[:] for item in graph]

cnt = 1
result1 = 0
result2 = 0
change = ""

for i in range(m):
    for j in range(n):
        if visited[i][j] == 'W':
            change = 'W'
            bfs(i, j)
            result1 += cnt * cnt    
            cnt = 1

visited = [item[:] for item in graph]
for i in range(m):
    for j in range(n):
        if visited[i][j] == 'B':
            change = 'B'
            bfs(i, j)
            result2 += cnt * cnt    
            cnt = 1

print(result1, result2)