백준 21736번: 헌내기는 친구가 필요해 [실버 3] - Python

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

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

 

풀이

 

DFS, 혹은 BFS로 풀 수 있겠습니다. 일단 저는 DFS로 먼저 접근해 보았는데요,

 

정답 코드 (DFS)

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]

visited = [[0] * m for _ in range(n)]
cnt = 0


def dfs(r, c):
    global cnt
    if r < 0 or r >= n or c < 0 or c >= m:
        return
    if visited[r][c] == 1:
        return
    if graph[r][c] == 'X':
        return
    visited[r][c] = 1
    if graph[r][c] == 'P':
        cnt += 1
    dfs(r - 1, c)
    dfs(r + 1, c)
    dfs(r, c - 1)
    dfs(r, c + 1)


start = (0, 0)
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            start = (i, j)

dfs(start[0], start[1])

if cnt == 0:
    print("TT")
if cnt != 0:
    print(cnt)

 

 

시간이 꽤나 오래 걸립니다. 캠퍼스 크기가 600x600이나 되어서 탐색하는 데 오래 걸리는 것 같네요. 게다가 기본으로 설정된 재귀 제한 1000으로는 택도 없는 것 같습니다. 그래서 꼭 sys.setrecursionlimit()함수를 써서 재귀제한을 늘려야 합니다.

저는 처음에 10,000으로 늘렸는데, 여전히 제한이 걸려서 100,000으로 늘렸다가 또 안 돼서 1,000,000으로 늘리니까 성공했습니다. 엄청 깊게 들어가는 것 같아요.

 

풀고 나서 다른 분들의 정답 코드를 봤는데, BFS로 푸신 분들은 저보다 약 1/3가량 속도가 빠르더라구요. 그래서 저도 BFS로도 다시 풀어봤습니다.

 

정답 코드 (BFS)

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]

visited = [[0] * m for _ in range(n)]
cnt = 0


def bfs(row, col):
    global cnt
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dq = deque()
    dq.append((row, col))
    visited[row][col] = 1
    while dq:
        r, c = dq.popleft()
        for i in range(4):
            nr = r + move[i][0]
            nc = c + move[i][1]
            if nr < 0 or nr >= n or nc < 0 or nc >= m:
                continue
            if graph[nr][nc] == 'X':
                continue
            if visited[nr][nc] == 1:
                continue
            visited[nr][nc] = 1
            dq.append((nr, nc))
            if graph[nr][nc] == 'P':
                cnt += 1

start = (0, 0)
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            start = (i, j)

bfs(start[0], start[1])

if cnt == 0:
    print("TT")
if cnt != 0:
    print(cnt)

 

BFS로 풀었더니? 역시나 시간도 1/3로 줄고 메모리도 절반 이상 줄었습니다. BFS가 DFS보다 전반적으로 속도가 빠르다고 하니, 그 영향인 것 같습니다.