PS
백준 21736번: 헌내기는 친구가 필요해 [실버 3] - Python
Alsong
2023. 11. 12. 16:46
풀이
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보다 전반적으로 속도가 빠르다고 하니, 그 영향인 것 같습니다.