[ProblemSolving] 백준 10026번 적록색약 문제풀이

백준 10026번 적록색약 문제풀이입니다. 문제 해설은 링크를 확인하면 된다. 문제 해설

10026번: 적록색약

해당 문제는 그래프 탐색 유형의 문제로 'G'를 'R'로 보는 적록색약인 사람이 보는 구역의 수와 적록색약이 아닌 사람이 보는 구역의 수를 구해야 한다. 해당 문제를 해결하기 위해서는 다음의 과정을 수행해야 한다. colorData는 입력받은 색 정보이다.

 

• colorData에서 BFS를 수행한다.
• 수행하면서 연산의 끝에 'G'를 'R'로 바꿔준다.
• 모든 'G'가 'R'로 변했다면 다시 BFS를 수행한다.
• 과정 1, 과정 3에서 수행한 결과를 출력해준다.

위의 과정을 코드로 작성하면 다음과 같다.

 

from collections import deque
 
def bfs(x, y, value):
  queue = deque()
  queue.append((x,y))
  visited[x][y] = True
 
  dx = [0, -1, 0, 1]
  dy = [-1, 0, 1, 0]
 
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx >= 0 and nx < n and ny >= 0 and ny < n:
        if not visited[nx][ny] and colorData[nx][ny] == value:
          visited[nx][ny] = True
          queue.append((nx,ny))
 
    if colorData[x][y] == "G":
      colorData[x][y] = "R"
 
n = int(input())
count = 0
visited = [[False] * n for _ in range(n)]
colorData = []
for i in range(n):
  colorData.append(list(str(input())))
 
for i in range(n):
  for j in range(n):
    if not visited[i][j]:
      count += 1
      bfs(i, j, colorData[i][j])
print(count, end=' ')
count = 0
 
for i in range(n):
  for j in range(n):
    visited[i][j] = False
 
for i in range(n):
  for j in range(n):
    if not visited[i][j]:
      count += 1
      bfs(i, j, colorData[i][j])
print(count)
      

 

이번 문제는 BFS 탐색 중에 데이터의 값을 바꿔준다는 것이 다른 BFS 문제와 차별점이 있었던 것 같다.