제자리에서 대하는 경우, 더미 데이터가 큐에 쌓이는 것을 방지하기 위해 해당 위치의 첫 방문 시점을 t라고 하면 t + 4 미만인 경우까지만 큐에 넣어준다.
진행하려는 방향마다 데이터를 삽입하지 않게 하기 위해 stay라는 boolean 변수를 사용.
다익스트라로도 구현이 가능하다.
다익스트라로 구현하는 경우, 제자리에서 대기하는 로직 대신 각 방향마다 t + wait time을 구현해서 삽입해주면 더 쉽게 구현이 가능하다.
파이썬
from collections import deque
import sys
# 함수 / 글로벌 변수
input = lambda: sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<W and 0<=y<H
cvt = {"E":0,"S":1,"W":2,"N":3}
dires = [(1,0), (0,1),(-1,0),(0,-1)]
while True:
# 입력
H,W = map(int, input().split())
if not W and not H:
break
arr = [list(map(cvt.get,input())) for _ in range(H)]
N = int(input())
find = (1<<N)-1
targets = [tuple(map(lambda i : int(i)-1, input().split()))[::-1] for _ in range(N)]
# 방문 배열 : 위치 1차원으로 압축
V = [[-1]*(H*W) for _ in range(1<<N)]
V[0][0] = 0
# location / state / time
Q = deque([(0,0,0)])
while Q:
l,s,t = Q.popleft()
y,x = divmod(l,W)
nt = t+1
# 도착
if x == W-1 and y == H-1 and s == find:
print(t)
break
# 현재 시점 t에 열려있는 방향
open_dire = (arr[y][x]+t)%4
stay = False
for dire,(dx,dy) in enumerate(dires):
nx,ny = x+dx,y+dy
nl = ny*W+nx
if not inside(nx,ny):
continue
# 해당 위치가 보물 위치이면 방문
ns = s
if (nx,ny) in targets:
ns |= 1 << targets.index((nx,ny))
# 열려있는 방향이고 첫 방문인 경우 방문하기
if open_dire == dire:
if V[ns][nl] == -1:
V[ns][nl] = nt
Q.append((nx+W*ny,ns,nt))
# 닫혀있는 방향이면, 현 위치 방문시각 + 4보다 작은 경우에 대기로직 구현
else:
if not stay and nt < V[s][l] + 4:
Q.append((x+W*y,s,nt))
stay = True
pypy TLE.
y x를 loc로 1차원 압축해도 TLE.
자바
import java.io.*;
import java.util.*;
public class Main {
static int H, W;
static int[][] arr;
static int[][] targets;
static final int[][] dires = {{1,0}, {0,1}, {-1,0}, {0,-1}};
static Map<Character, Integer> cvt = new HashMap<>() {{
put('E', 0);
put('S', 1);
put('W', 2);
put('N', 3);
}};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
if (W == 0 && H == 0) break;
arr = new int[H][W];
for (int i = 0; i < H; i++) {
String line = br.readLine();
for (int j = 0; j < W; j++) {
arr[i][j] = cvt.get(line.charAt(j));
}
}
int N = Integer.parseInt(br.readLine());
int find = (1 << N) - 1;
targets = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
targets[i][0] = x;
targets[i][1] = y;
}
int[][][] V = new int[1 << N][H][W];
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < H; j++) {
Arrays.fill(V[i][j], -1);
}
}
V[0][0][0] = 0;
ArrayDeque<int[]> Q = new ArrayDeque<>();
Q.offer(new int[]{0, 0, 0, 0});
while (!Q.isEmpty()) {
int[] cur = Q.poll();
int x = cur[0], y = cur[1], s = cur[2], t = cur[3];
int nt = t + 1;
if (x == W-1 && y == H-1 && s == find) {
System.out.println(t);
break;
}
int openDire = (arr[y][x] + t) % 4;
boolean stay = false;
for (int dire = 0; dire < 4; dire++) {
int nx = x + dires[dire][0];
int ny = y + dires[dire][1];
if (!inside(nx, ny)) continue;
int ns = s;
for (int i = 0; i < targets.length; i++) {
if (nx == targets[i][0] && ny == targets[i][1]) {
ns |= 1 << i;
break;
}
}
if (openDire == dire) {
if (V[ns][ny][nx] == -1) {
V[ns][ny][nx] = nt;
Q.offer(new int[]{nx, ny, ns, nt});
}
} else {
if (!stay && nt < V[s][y][x] + 4) {
Q.offer(new int[]{x, y, s, nt});
stay = true;
}
}
}
}
}
}
static boolean inside(int x, int y) {
return 0 <= x && x < W && 0 <= y && y < H;
}
}
댓글