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

백준 10026번 <적록색약> 문제 보기

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

10026번: 적록색약

 

백준 10026번 <적록색약> 문제 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

from collections import deque

n = int(input())
array = [list(map(str, input().strip())) for _ in range(n)]

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

visited = [[False]*n for _ in range(n)]
queue = deque()

def dfs(x, y):
  queue.append((x, y))
  
  while queue:
    x, y = queue.popleft()
    value = array[x][y]

    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]==False:
        if array[nx][ny] == value:
          visited[nx][ny] = True
          dfs(nx, ny)


check = 0
for i in range(n):
  for j in range(n):
    if visited[i][j] == False:
      dfs(i, j)
      check += 1

print(check, end = " ")

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

visited = [[False]*n for _ in range(n)]

check = 0
for i in range(n):
  for j in range(n):
    if visited[i][j] == False:
      dfs(i, j)
      check += 1

print(check)

DFS(깊이 우선 탐색) 알고리즘이다. 탐색 가능한 부분까지 전부 DFS를 재귀로 진행한다. visited가 false인 곳을 탐색하며 영역이 몇개인지 개수를 셀 수 있다. 일반 사람들 기준으로 개수를 세고, R을 G로 전부 바꾸거나 G를 R로 전부 바꾼 후 적록색약 사람들 기준으로 개수를 세어 두 값을 반환하면 된다.