[백준] 10026번 적록색약 - 파이썬(Python)

문제 (링크)

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

10026번: 적록색약

 

나의 풀이

from collections import deque
visited = [[False] * n for _ in range(n)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
graph = [[] * n for _ in range(n)]

for i in range(n):
	color = str(input())
    for x in color:
    	graph[i].append(x)

def bfs(x, y, color):
	q = deque()
    q.append([x, y])
    
    while q:
    	loc = q.popleft()
        x = loc[0]
        y = loc[1]
        
        if visited[x][y] == False:
        	visited[x][y] = True
        	for i in range(4):
        		nx, ny = x + move[i][0], y + move[i][1]
        		if nx >= 0 and nx < n and ny >= 0 and ny < n:
	                if graph[nx][ny] == color:
                    	q.append([nx, ny])

# 색약 아닐 때
cnt = 0
for i in range(n):
	for j in range(n):
    	if visited[i][j] == False:
        	color = graph[i][j]
            bfs(i, j, color)
            cnt += 1

# 색약일 때
visited = [[False] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
    	if graph[i][j] == 'G':
        	graph[i][j] = 'R'

cnt_color_weakness = 0
for i in range(n):
	for j in range(n):
    	if visited[i][j] == False:
        	color = graph[i][j]
            bfs(i, j, color)
            cnt_color_weakness += 1

print(cnt)
print(cnt_color_weakness)

풀이법 및 코드 설명

보자마자 BFS 생각이 나는 문제이다. 일반적인 다른 BFS 탐색과 다른 점은 그래프 내에서 이동할 수 있는 조건이 3개라는 점이다.

 

따라서 bfs에 parameter로 color를 추가해서 graph[nx][ny]의 값을 해당 color와 비교해 같은 색상이면 이동할 수 있고, 다르면 이동할 수 없도록 처리해주었다.

 

색약인 경우, 'G'와 'R'을 같은 것으로 처리해주어야하므로 bfs함수를 따로 만들어줘야하나 생각했다가, 그냥 graph를 순회하면서 'G'를 모두 'R'로 바꿔버린 후 동일한 bfs함수를 사용하는 것으로 풀었다.