백준 25319번: Twitch Plays VIIIbit Explorer

문제링크

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

문제 총평

- 간단한 구현 문제, 단 BFS 또는 DFS로 오해하면 안된다.

문제 접근방식

- 문제를 보자마자는 DFS 또는 BFS로 생각했지만 시간복잡도가 너무 클거같다고 생각함.

- 어처피 스페셜 저지 문제이고 최소값을 구할 필요가 없으므로 가능한 경우 무조건 그 장소로 가도록 하였음

정답코드

import sys;I = sys.stdin.readline
from collections import defaultdict
n,m,l = map(int,I().rstrip().split())
arr = [list(I().rstrip()) for _ in range(n)]
s = I().rstrip()
dic = defaultdict(list)
for i in range(n):
    for j in range(m):
        dic[arr[i][j]].append((i,j))
x,y = 0,0
idx = 0
num = [0,0]
ans = []
tem = []
dx = [0,'R','L']
dy = [0,'D','U']
tx,ty = 0,0
while 1:
    try:
        nx,ny = dic[s[idx]].pop()
    except:
        break
    for i in range(abs(nx-x)):
        tem.append(dy[(nx-x)//abs(nx-x)])
    for i in range(abs(ny-y)):
        tem.append(dx[(ny-y)//abs(ny-y)])
    x,y = nx,ny
    tem.append('P')
    idx += 1
    if idx == len(s):
        num[0] += 1
        idx = 0
        ans.extend(tem)
        num[1] += len(tem)
        tem = []
        tx,ty = x,y
if num[0] == 0:
    x,y = 0, 0
    num = [0,0]
x,y = tx,ty
for i in range(n-x-1):
    ans.append('D')
for i in range(m-y-1):
    ans.append('R')
num[1] += n-x + m-y - 2
print(*num)
print(''.join(ans))

 

풀이 방법

- arr를 미리 받은 후 모든 문자의 위치를 각각의 딕셔너리에 저장함

- 이때 정답에 맞는 알파벳의 위치로 무조건 가도록 하고 현재 위치에서 그 알파벳의 위치까지 가는 경로를 정답에 표시해 주면 됨

- 이때 중요한 점은 오른쪽 아래로 가서 문제를 끝낼 때 아이템을 하나도 가지고 있으면 안되므로 무조건 ID를 완성할 수 있는 경우에만 경로와 위치를 저장

 

문제 풀이 후 생각

- 문제를 잘 읽어야 한다.

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요