[백준(python)] 10026_적록색약

📌 난이도, 유형

난이도 : 골드5
유형 : 그래프 이론, 그래프 탐색, BFS, DFS
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

import copy
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
graph = []
for i in range(1, N + 1):
    graph.append(list(map(str, input())))

# 적록색약
graph2 = copy.deepcopy(graph)
result = 0
result2 = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]

# 정상인
def bfs(color, x, y):
    queue = deque()
    graph[x][y] = 0
    queue.append((color,x,y))
    while queue:
        color, x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == color:
                graph[nx][ny] = 0
                queue.append((color, nx, ny))
    return 1

# 적록색약
def bfs2(color, x, y):
    queue2 = deque()
    graph2[x][y] = 0
    queue2.append((x, y))
    while queue2:
        x, y = queue2.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or graph2[nx][ny] == 0:
                continue
            if color == 'B' and graph2[nx][ny] == color:
                graph2[nx][ny] = 0
                queue2.append((nx, ny))
            if color != 'B' and graph2[nx][ny] in ['G', 'R']:
                graph2[nx][ny] = 0
                queue2.append((nx, ny))
    return 1

for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            result += bfs(graph[i][j], i,j)
        if graph2[i][j] !=0:
            result2 += bfs2(graph2[i][j],i,j)
print(result)
print(result2)

---

📝 해설

그래프에서 G랑 R을 같은색으로 만들어 주면 쉽게 풀 수 있는 문제이지만 바꾸지 않고 풀어보기로 했다.

(너비우선탐색 사용)

deepcopy(깊은복사)를 사용해서 똑같은 그래프를 하나 생성
(얕은복사를 하면 graph를 수정했을 때 graph2까지 영향을 주기 때문에 깊은복사를 해줬음)

import copy
graph2 = copy.deepcopy(graph)

서로 다른 그래프에서 동작할 수 있게 조건문으로 나눠주었다.

for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            result += bfs(graph[i][j], i,j)
        if graph2[i][j] !=0:
            result2 += bfs2(graph2[i][j],i,j)

정상인일 경우에는 원래 사용하던 방법 그대로 사용

def bfs(color, x, y):
    queue = deque()
    graph[x][y] = 0
    queue.append((color,x,y))
    while queue:
        color, x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == color:
                graph[nx][ny] = 0
                queue.append((color, nx, ny))
    return 1

적록색약일 경우

if color == 'B' and graph2[nx][ny] == color:
  graph2[nx][ny] = 0
  queue2.append((nx, ny))
if color != 'B' and graph2[nx][ny] in ['G', 'R']:
  graph2[nx][ny] = 0
  queue2.append((nx, ny))

B일 때랑 B가 아닐 때를 나눠주었다.