Easy is Perfect

[백준] 10026번 풀이 _ 적록색약

  • melonicedlatte
  • Mar 30, 2020


1. 문제

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

2. 풀이 방법

모든 row와 col 을 살펴보면서 해당 블록의 주변에 있는 요소들이 같은 색일 경우에 방문한 것으로 체크하고, dfs를 통하여 상하좌우 요소들을 모두 살펴봅니다.

3. 주의 사항

import sys
sys.setrecursionlimit(100000)

python은 재귀함수 호출 횟수가 제한되어 있어(1000회) 그 횟수를 늘려주기 위한 메소드를 사용해야 문제에서 런타임 에러가 나지 않습니다.

4. 소스코드

import sys
sys.setrecursionlimit(100000)

N = int(input())
sec_num = sec_num2 = 0 
is_visited = [[0] * N for x in range(N)] 
this_map = [] 

for i in range(N): 
  this_map.append([x for x in input()]) 

def confirm(row, col, now_color):
  if row < 0 or row >= N or col < 0 or col >= N:
    return 

  if is_visited[row][col] == 1:
    return
 
  if this_map[row][col] is now_color:
    is_visited[row][col] = 1
    confirm(row - 1, col, now_color)
    confirm(row + 1, col, now_color)
    confirm(row, col - 1, now_color)
    confirm(row, col + 1, now_color)
  else:
    return

for row in range(N):
  for col in range(N):
    if is_visited[row][col] == 0:
      confirm(row, col, this_map[row][col])
      sec_num += 1

## init ## 
for row in range(N):
  for col in range(N):
    if this_map[row][col] == 'R':
      this_map[row][col] = 'G'

is_visited = [[0] * N for x in range(N)] 

for row in range(N):
  for col in range(N):
    if is_visited[row][col] == 0:
      confirm(row, col, this_map[row][col])
      sec_num2 += 1

print(sec_num, sec_num2)



Search