21772 고구마 먹방
문제
가희는 고구마를 정말 좋아합니다.
이번에도 어김 없이 고구마 냄새가 났는데, 고구마가 보이지 않습니다. 오빠가 방 안에 고구마를 숨겨 놓았기 때문입니다.
오빠는 가희에게 하나의 게임을 제안하고, 게임의 규칙을 설명해 주었습니다. 게임 규칙은 아래와 같습니다.
가희는 1초마다 상하좌우 방향 중 한 방향으로 1번 이동하거나, 이동하지 않고 그 자리에 머무를 수 있습니다.
가희가 이동한 지점에 고구마가 있는 경우에는, 고구마를 먹습니다. 고구마를 먹는 데 걸리는 시간은 없다고 가정합니다.
가희가 고구마를 먹으면, 고구마가 다시 그 자리에 생기지 않습니다.
가희는 현재 위치에서 T초만큼 이동했을 때 고구마를 최대한 많이 먹고 싶습니다. 가희가 최대 몇 개의 고구마를 먹을 수 있는지 알려주세요.
입력
첫 번째 줄에 맵의 세로 크기 R, 가로 크기 C, 가희가 이동하는 시간 T가 주어집니다.
두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다.
주어지는 문자열에 있는 문자는 가희를 나타내는 'G', 고구마를 나타내는 'S', 빈 칸을 나타내는 '.', 장애물을 나타내는 '#' 중 하나 입니다.
출력
문제에 대한 답을 출력합니다.
제한
2 ≤ R ≤ 100
2 ≤ C ≤ 100
1 ≤ T ≤ 10
가희를 나타내는 문자인 'G'는 맵 안에 하나만 있습니다. 'G'가 있는 위치는, 가희의 현재 위치입니다.
'S'가 있는 위치에 고구마는 1개 있습니다.
고구마와 장애물은 최소 1개 이상 있습니다.
가희는 장애물을 뛰어 넘거나 통과할 수 없습니다.
가희는 맵 밖으로 나갈 수 없습니다.
풀이
간단한 미로찾기 로직과 비슷하다 . 조금씩 꼬아 낸 문제
1) 입력받기 ....#..S.. 이런 식으로 입력을 받은 걸 리스트로 띄워 받아야 했다.
2) 먹은 곳을 돌아갈 수 있다는 조건이 어려웠다. dfs 안에 변수로 visited 를 받아 새로 초기화된 visited도 넣을 수 있게 만들었다.
3) count가 안끝나면 result가 비어있게 된다 -> 처리해주기
↓고구마를 먹는 순간 visit 초기화해서 다시 돌아갈 수 있게 만들기
import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
R,C,T = map(int,input().split()) # 입력받기
graph =[]
for _ in range(R):
ls =[] # 한 글 자 씩 받 는 법
ls.extend(input())
if '\n' in ls: # 마지막에 띄워쓰기가 있다면
ls.remove('\n') # 지워주고
graph.append(ls) # 그 리스트를 넣어준다
gahee = [0,0] # 가희가 있는 곳
for i in range(R):
for j in range(C):
if graph[i][j]=='G':
graph[i][j]='.' # 찾아서 빈 곳으로 만들어 주고
gahee = [i,j] # 위치를 저장한다.
visit = [[0]*C for _ in range(R)] # 방문 처리용
visit[gahee[0]][gahee[1]] = 1 # 가희를 방문처리 먼저 해주기
result = [] # 결과 창
def dfs(y,x,time,potato,visit): # dfs 를 돌면서 (내위치,남은기회,먹은개수,방문유무확인용)
if time == 0: # 갈수있는 기회가 없다면
result.append(potato) # 먹은개수를 결과에 넣는다
return
dy = [0,0,1,-1] # 네방향 순회하면서
dx = [1,-1,0,0]
for i in range(4):
ny,nx = dy[i]+y , dx[i]+x
if 0<=ny<R and 0<=nx<C: # 범위내에있고
if graph[ny][nx]=='.' and visit[ny][nx]==0: # 길이 열려있고 방문 안했다?
visit[ny][nx]=1 # 방문 시키고
dfs(ny,nx,time-1,potato,visit) # dfs 순회를 하는데
visit[ny][nx]=0 # 순회가 끝나면 방문처리철회
if graph[ny][nx]=='S' and visit[ny][nx]==0: # 고구마라면?
graph[ny][nx]='.' # 먹었다! 먹은자리 비우기
newvisit = [[0]*C for _ in range(R)] # 중요한 로직
# 고구마를 먹고나면 모든 방문 처리를 다 없애서 다시 돌아갈 수 있도록 만들기
dfs(ny,nx,time-1,potato+1,newvisit) # 새로운 visit를 넣어준다
graph[ny][nx]='S' # 고구마 다시 생기기
dfs(gahee[0],gahee[1],T,0,visit)
if len(result)==0: # 이거 때문에 valueerror 났었음
print(0) # count가 남았는데 끝나면 result가 비게된다.
else:
print(max(result)) # 최고값 구해주기
```
Author And Source
이 문제에 관하여(21772 고구마 먹방), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bbnerino/21772-고구마-먹방저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)