[백준 10026] 적록색약 (Python)

👩🏻‍💻문제링크

[백준 10026] 적록색약 (Python)

✍️Idea Sketch

2021-08-03

1. 문제가 요구하는 출력값은?

1. 적록색약이 아닌 사람은 R, G, B 세 종류로 구역을 나눈다.
2. 적록색약인 사람은 R=G, B 두 종류로 구역을 나눈다.
3. 두 사람이 인지하는 구역의 수를 각각 출력해야 한다.

2. main 로직

• 입력값을 받아 graph를 작성한다.
• 방문여부를 저장하는 visited를 작성한다.
• 모든 color를 방문하므로 이중 반복문을 사용한다.

for i in range(n):
  for j in range(m):
    # graph[i][j]

• 적록색약이 아닌 사람
  1) 처음 방문한 경우, 새로운 구역을 인지한 것이다.
  2) 따라서 result += 1 을 실행한다.
• 적록색약인 사람
  0) color가 'G'인 경우, 'R'로 인지한다.
  1) 처음 방문한 경우, 새로운 구역을 인지한 것이다.
  2) 따라서 result += 1 을 실행한다.

3. DFS 로직

• 경계값을 분석한다.
• 방문여부를 확인한다.
• 방문한 color가, main에서 새로운 구역을 인지했을 때 color와 일치하는지 확인한다.
  2-(1) 에서 새로운 구역을 인지했을 때
• 방문 처리를 한다.
• 상하좌우에 인접한 color를 방문한다.

✍️소스코드

2021-08-03

112ms 통과

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, color):
  if (0<=x<n) and (0<=y<n):
    if visited[x][y] == 0:
      if graph[x][y] == color:
        visited[x][y] = 1
        dfs(x-1, y, color)
        dfs(x+1, y, color)
        dfs(x, y-1, color)
        dfs(x, y+1, color)
        return True
  return False

def dfs_color(x, y, color):
  if (0<=x<n) and (0<=y<n):
    if visited[x][y] == 0:
      if (graph[x][y] == color) or (color == 'R' and graph[x][y] == 'G'):
        visited[x][y] = 1
        dfs_color(x-1, y, color)
        dfs_color(x+1, y, color)
        dfs_color(x, y-1, color)
        dfs_color(x, y+1, color)
        return True
  return False

if __name__ == '__main__':
  n = int(input())
  graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]

  # 적록색약이 아닌 사람
  visited = [[0 for _ in range(n)] for _ in range(n)]
  result = 0

  for i in range(n):
    for j in range(n):
      if dfs(i, j, graph[i][j]) == True:
        result += 1

  print(result, end=' ')

  # 적록색약인 사람
  visited = [[0 for _ in range(n)] for _ in range(n)]
  result = 0

  for i in range(n):
    for j in range(n):
      if graph[i][j] == 'G':
        graph[i][j] = 'R'
      if dfs_color(i, j, graph[i][j]) == True:
        result += 1

  print(result)

main 리팩토링 후 120ms 통과

• for문으로 main의 중복 코드 리팩토링

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, color):
  if (0<=x<n) and (0<=y<n):
    if visited[x][y] == 0:
      if graph[x][y] == color:
        visited[x][y] = 1
        dfs(x-1, y, color)
        dfs(x+1, y, color)
        dfs(x, y-1, color)
        dfs(x, y+1, color)
        return True
  return False

def dfs_color(x, y, color):
  if (0<=x<n) and (0<=y<n):
    if visited[x][y] == 0:
      if (graph[x][y] == color) or (color == 'R' and graph[x][y] == 'G'):
        visited[x][y] = 1
        dfs_color(x-1, y, color)
        dfs_color(x+1, y, color)
        dfs_color(x, y-1, color)
        dfs_color(x, y+1, color)
        return True
  return False

if __name__ == '__main__':
  n = int(input())
  graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]

  for man in range(2):
    visited = [[0 for _ in range(n)] for _ in range(n)]
    result = 0

    for i in range(n):
      for j in range(n):

        if man == 0:  # 적록색약이 아닌 사람
          if dfs(i, j, graph[i][j]) == True:
            result += 1

        else:  # 적록색약인 사람
          if graph[i][j] == 'G':
            graph[i][j] = 'R'
          if dfs_color(i, j, graph[i][j]) == True:
            result += 1

    print(result, end=' ')