[백준] 21736 헌내기는 친구가 필요해

풀이

dfs 를 사용하면 600*600 배열의 경우, 깊이가 많이 깊어져서 시간 초과(+스택 오버플로우 가능성)가 나는 것 같다.

+) input = sys.stdin.readline 이것을 사용하면 dfs로도 시간초과를 해결할 수 있었다. 그래도 bfs 가 훨씬 더 빠르다.

dfs 시간초과 1

import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
arr =[]
s,e = -1,-1
cnt = 0
for _ in range(n): arr.append(list(input()))
# 시작점 찾음
for i in range(n): 
    for j in range(m): 
        if arr[i][j] == 'I': s,e=i,j

# 갈 수 있는 방향인지 확인
def check(r,c):
    global cnt
    if r >= 0 and r < n and c>=0 and c< m and (arr[r][c] == 'P' or arr[r][c] == 'O'):
        if arr[r][c] == 'P': cnt+=1 # 새로운 사람인 경우
        return True
    else: return False

#dfs, 방문 한것 A(Already visited) 로 처리
def dfs(r,c):
    dir = [[-1,0],[0,1],[1,0],[0,-1]]
    for dr, dc in dir:
        if check(r+dr,c+dc):
            arr[r+dr][c+dc] = "A" # 방문처리
            dfs(r+dr,c+dc)
dfs(s,e)
if cnt == 0: print("TT")
else: print(cnt)

dfs 시간초과 2

 for dr, 업으로부터  in dir:
        nr,nc = r+dr,c+dc

위에서 r+dr,c+dc를 r,c로 받으면 다른 방향에서의 좌표가 이전에 수행된 작업으로부터 영향을 받아버림

import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
arr =[]
s,e = -1,-1
cnt = 0
for _ in range(n): arr.append(list(input()))
# 시작점 찾음
for i in range(n):
    isFind = False 
    for j in range(m): 
        if arr[i][j] == 'I': 
            s,e=i,j
            isFind = True
            break
    if isFind == True: break

#dfs, 방문 한것 A(Already visited) 로 처리
def dfs(r,c):
    global cnt
    dir = [[-1,0],[0,1],[1,0],[0,-1]]
    for dr, dc in dir:
        nr,nc = r+dr,c+dc
        if nr < 0 or nr >= n or nc < 0 or nc >= m: continue
        if arr[nr][nc] == 'X' or arr[nr][nc] == 'A' or arr[nr][nc] == 'I': continue
        if arr[nr][nc] == 'P': cnt+=1 # P인 경우
        arr[nr][nc] = "A" # 방문처리
        dfs(nr,nc) # 방문
dfs(s,e)
if cnt == 0: print("TT")
else: print(cnt)

bfs 시간초과 X

from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
arr =[]
s,e = -1,-1
cnt = 0
for _ in range(n): arr.append(list(input()))
# 시작점 찾음
for i in range(n):
    isFind = False 
    for j in range(m): 
        if arr[i][j] == 'I': 
            s,e=i,j
            isFind = True
            break
    if isFind == True: break

def bfs(r,c):
    global cnt
    queue = deque()
    queue.append((r,c)) # 시작 좌표(I) 넣음
    
    while queue:
        pr,pc = queue.popleft()
        dir = [[-1,0],[0,1],[1,0],[0,-1]]
        for dr, dc in dir:
            nr,nc = pr+dr,pc+dc
            if nr < 0 or nr >= n or nc < 0 or nc >= m: continue
            if arr[nr][nc] == 'X' or arr[nr][nc] == 'A' or arr[nr][nc] == 'I': continue
            if arr[nr][nc] == 'P': cnt+=1 # P인 경우
            arr[nr][nc] = "A" # 방문처리
            queue.append((nr,nc)) # 방문
bfs(s,e)
if cnt == 0: print("TT")
else: print(cnt)