백준 알고리즘 10026번: 적록색약(Python)

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

10026번: 적록색약

---

문제 해결을 위한 과정

이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.

그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.

위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.

---

문제 해결을 위한 팁

저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.

---

소스코드

from collections import deque
import copy
 
def bfs(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.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:
        continue
      if graph[nx][ny] == target:
        graph[nx][ny] = 'a'
        q.append((nx, ny))
 
def bfs2(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.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:
        continue
      if target == 'R' or target == 'G':
        if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      else:
        if graph[nx][ny] == target:
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      
        
 
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
  inputData = list(input()) 
  for j in range(n):
    graph[i][j] = inputData[j]
 
graph2 = copy.deepcopy(graph)
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
count = 0
for i in range(n):
  for j in range(n):
    if graph[i][j] != 'a':
      bfs(graph, i, j)
      count += 1
 
print(count, end=" ")
 
count = 0
for i in range(n):
  for j in range(n):
    if graph2[i][j] != 'a':
      bfs2(graph2, i, j)
      count += 1
 
print(count)