10026번: 적록색약

 

 

 

풀이

 

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

 

 

dfs

...

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

 

visited[x][y]가 R,G,B중 하나에 해당한다면 해당값으로 color의 값을 바꿔줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 visited[nx][ny] == color 라면 dfs를 재호출 합니다.

 

주위에 같은색이 없다면 그림이 연결돼있는 구역을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

 

적록색약인 경우 'G'를 'R'로 바꿔주고 탐색합니다.

...

 

 

 

bfs

...

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

 

visited[x][y]가 R,G,B중 하나에 해당한다면 해당값으로 color의 값을 바꿔줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 visited[nx][ny] == color 라면 방문처리한뒤 queue에 nx,ny 값을넣어줍니다.

 

주위에 같은색이 없다면 그림이 연결돼있는 구역을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

 

적록색약인 경우 'G'를 'R'로 바꿔주고 탐색합니다.

...

 

 

 

 

파이썬 dfs

from collections import deque
import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global color
    if visited[x][y] == 'R': color = 'R'
    elif visited[x][y] == 'G': color = 'G'
    elif visited[x][y] == 'B': color = 'B'
    visited[x][y] = 'V'

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

        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == color:
            dfs(nx, ny)

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

color = ""
cnt = 0
cntCb = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] not in 'V':
            dfs(i, j)
            cnt += 1

visited = [item[:] for item in graph]
for i in range(n):
    for j in range(n):
        if visited[i][j] == 'G':
            visited[i][j] = 'R' 

for i in range(n):
    for j in range(n):
        if visited[i][j] not in 'V':
            dfs(i, j)
            cntCb += 1 

print(cnt, cntCb)

 

 

 

파이썬 bfs

from collections import deque
import sys

def bfs(x, y):
    global color
    if visited[x][y] == 'R': color = 'R'
    elif visited[x][y] == 'G': color = 'G'
    elif visited[x][y] == 'B': color = 'B'

    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 < n and 0 <= ny < n and visited[nx][ny] == color:
                visited[nx][ny] = 'V'
                queue.append((nx, ny))

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

color = ""
cnt = 0
cntCb = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] not in 'V':
            bfs(i, j)
            cnt += 1

visited = [item[:] for item in graph]
for i in range(n):
    for j in range(n):
        if visited[i][j] == 'G':
            visited[i][j] = 'R' 

for i in range(n):
    for j in range(n):
        if visited[i][j] not in 'V':
            bfs(i, j)
            cntCb += 1 
                       
print(cnt, cntCb)