[DFS] 백준_적록색약 + sys.setRecursion, sys.stdin.readline, rstrip
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
이 문제는 사이클을 확인해서 구역의 개수를 세는 문제이기 때문에 DFS가 적합합니다.
DFS와 BFS 문제를 구분하는 방법은 아래 글에서 자세히 설명해두었습니다!
[DFS & BFS] 음료수 얼려먹기 + 2차원 리스트 생성 및 입력 방법
2차원 리스트 생성 및 입력 방법 0. 0으로 채워진 2차원 리스트 생성하기 my_list = [[0 for _ in range(n)] for _ in range(0)] #0으로 이루어진 2차원 리스트 생성 * for 문에서 _는 변수 지정 없이 반복할 때 사용
blu-blu.tistory.com
그럼 이제 문제 풀이 시작하도록 하겠습니다.
import sys
sys.setrecursionlimit(10**6) # 파이썬의 재귀 깊이 지정 (Python3)
input = sys.stdin.readline
n = int(input())
rgb = []
for i in range(n):
rgb.append(list(input().rstrip()))
visited = [[False]*n for _ in range(n)]
p1 = 0 #적록색약이 아닌 사람
p2 = 0 #적록색약인 사람
# 상하좌우 #상:(-1,0), 하:(1,0), 좌:(0,-1), 우:(0,1)
dx = [-1, 1, 0, 0] # 행 이동
dy = [0, 0, -1, 1] # 열 이동
def dfs(x,y):
#현재노드 방문처리
visited[x][y] = True
#현재노드 색 저장
color = rgb[x][y]
for i in range(4):
# nx, ny : 현재노드에서 이동할 상하좌우 노드
nx = x+dx[i]
ny = y+dy[i]
#맵을 벗어나지 않는 경우
if (nx<n and nx>=0 and ny>=0 and ny<n):
#아직 방문하지 않았고, 같은 색인 경우(==같은 공간인 경우)
if visited[nx][ny]==False and rgb[nx][ny]==color:
#이동할 노드로 dfs 재귀
dfs(nx,ny)
# 적록색약이 아닌 경우
for x in range(n):
for y in range(n):
if visited[x][y] == False: #방문하지 않은 곳 탐색
dfs(x,y)
p1+=1
# 적록색약인 경우를 위해 r과 g을 하나로 통일함
for x in range(n):
for y in range(n):
if rgb[x][y]=='R':
rgb[x][y]='G'
# 위에서 통일하며 방문하였기 때문에 방문 리스트 초기화
visited = [[False]*n for _ in range(n)]
# 적록색약인 경우
for x in range(n):
for y in range(n):
if visited[x][y] == False: #방문하지 않은 곳 탐색
dfs(x,y)
p2+=1
print(p1, p2)이 문제를 풀기 위한 아이디어는 다음과 같습니다!
1. DFS을 이용하여 같은 구역(같은 색깔)의 개수를 구한다.
2. R과 G를 하나로 통일한 후 적록색약인 사람에게 보이는 같은 구역(같은 색깔)의 개수를 구한다.
3. 방문리스트와 방향벡터 사용!
런타임에러가 나서 갱장이 당황했는데요!
재귀의 깊이가 깊을 것 같다싶으면 sys.setRecursion 함수를 사용해야한다고 합니다!
sys.setrecursionlimit() 함수는 Python에서 재귀 호출의 최대 깊이를 설정하는 데 사용됩니다. 재귀 호출이 너무 깊어지면 Python은 "RecursionError: maximum recursion depth exceeded"와 같은 오류를 발생시키기 때문에 이를 통해 한계를 정해주었습니다.
또한 혹시 몰라서 sys.stdin.readline을 사용해주었습니다.
sys.stdin.readline을 매번 타이핑하기엔 시간도 아깝고 익숙하지 않아서 input이라는 변수에 담아 함수처럼 사용해주었습니다!!
input()을 호출하면 sys.stdin.readline()을 호출한 것과 같은 동작을 수행할 수 있는 것입니다!!
rstrip은 오른쪽 공백을 삭제하는 함수 입니다. lstrip()은 왼쪽 공백 삭제, strip()은 왼쪽과 오른쪽 공백을 삭제할 수 있습니다.