[BOJ/백준] 21772 가희와 고구마 먹방

from collections import deque
import sys
 
R,C,T = map(int,input().split())
 
 
arr = []
start = []
for x in range(R):
    temp = list(input())
 
    for y in range(C):
        if temp[y] == 'G':
            start = (x,y)
 
    arr.append(temp)
 
 
stack = []
 
stack.append((*start,0,set()))
time = 0
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while time<T:
    new_stack = []
    for x,y,eat,visited in stack:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<R and 0<=ny<C:
                if arr[nx][ny] == 'S' and (nx,ny) not in visited:
                    new_visited = set()
                    new_visited.add((nx,ny))
                    new_visited = new_visited | visited
                    new_stack.append((nx,ny,eat+1,new_visited))
                    result = max(eat+1,result)
                elif arr[nx][ny] != '#':
                    new_stack.append((nx,ny,eat,visited))
    stack = [row[:] for row in new_stack]
    time += 1
 
print(result)
    
 

 

 

대회때 풀었던 풀이는 다음과 같다 BFS를 해주면서, 모든 이동경로를 누적해줬다.

 

그리고 visited에 없는 경우에만 고구마를 먹도록 해줬다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def dfs(node,time,eat):
    global T,result,R,C
    if time == T:
        result = max(result,eat)
        return
    else:
        result = max(result,eat)
        for i in range(4):
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if 0<=nx<R and 0<=ny<C and not vistied[nx][ny]:
                vistied[nx][ny] = True
                if arr[nx][ny] == 'S':
                    dfs((nx,ny),time+1,eat+1)
                else:
                    dfs((nx,ny),time+1,eat)
                vistied[nx][ny] = False
            elif 0<=nx<R and 0<=ny<C and vistied[nx][ny] and arr[nx][ny] !='#':
                dfs((nx,ny),time+1,eat)
 
R,C,T = map(int,input().split())
result = 0
vistied = [[False for _ in range(C)] for _ in range(R)]
 
 
arr = []
start = []
for x in range(R):
    temp = list(input())
    for y in range(C):
        if temp[y] == '#':
            vistied[x][y] = True
        elif temp[y] == 'G':
            start = (x,y)
    arr.append(temp)
 
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
dfs(start,0,0)
print(result)

대회가 끝나고 난뒤의 풀이이다.

 

dfs를 해주는데 바문을 최초로 한 경우의 S일때에만 고구마를 먹도록 했다.

 

그리고, 방문을 했지만, 벽만 아니라면, 지나갈수 있도록 만들어줬다.