[백준 21736] 헌내기는 친구가 필요해 (파이썬 풀이)

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

21736번: 헌내기는 친구가 필요해

제출 코드

import sys
sys.setrecursionlimit(10**6) # 재귀 제한 늘이기
input = sys.stdin.readline

def dfs(x,y):
    global cnt
    visited[x][y] = True
    if graph[x][y] == 'P':
        cnt+=1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
            if graph[nx][ny] !="X":
                dfs(nx,ny)


dx = [-1,1,0,0]
dy = [0,0,-1,1]
cnt = 0
n,m = map(int,input().split())
graph = list(input() for _ in range(n))
visited = [[False]*m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j]=="I":
            dfs(i,j)
if cnt==0:
    print("TT")
else:
    print(cnt)

- dfs로 풀었다. 도연이가 있는 위치를 기준으로 상하좌우를 살피며 깊이우선탐색을 진행하였고 전역변수 cnt로 만날 수 있는 사람의 수를 계산하였다. 기본적인 그래프 문제로 백준에 이와 비슷한 문제가 많다.

 

- 파이썬은 기본 재귀 깊이가 1000으로 매우 얕다. 따라서 재귀함수를 사용할 시 setrecursionlimit() 함수를 써서 늘려야 런타임 에러 (RecursionError)가 나지 않는다.