같은 위치에 도착하더라도 어떤 방향이고, 어떤 가속도로 왔냐에 따라서 다음 노드로 가는데 영향을 준다.
가속도는 최대 15까지 가능하다 (15 이상이면 한 방향으로 계속 달렸다는건데, 이 때 항상 맵 밖을 넘어가게 되어있다) -> 16까지 설정해서 가속도가 0~15까지 처리
동적으로 할당하는게 성능적으로는 가장 좋아보이는데 별로 안커서 그냥 할당함
파이썬
from collections import deque
import sys
input = lambda: sys.stdin.readline().strip()
# 내부 체크 / 첫 방문 / 방향
inside = lambda x,y: 0<=x<N and 0<=y<N
first = lambda x,y,d,a: V[a][d][y][x] == -1
dire = [(1,0),(0,1),(-1,0),(0,-1)]
# 입력 받기
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
accel = 16
# 4차원 배열 : 가속도가 15가 넘어가면 항상 맵 밖으로 넘어가기 때문에
V = [[[[-1]*N for _ in range(N)] for _ in range(4)] for _ in range(accel)]
Q = deque([])
for nd in range(2):
Q.append((0,0,nd,0))
V[0][nd][0][0] = 0
while Q:
x,y,d,a = Q.popleft()
nt = V[a][d][y][x] + 1
for nd,(dx,dy) in enumerate(dire):
# 이전 방향과 같아서 가속도가 붙는 경우
if nd == d:
# 일단 도착 지점에 도달 가능한지 확인한다.
nax,nay = x+dx*(a+1),y+dy*(a+1)
# 맵 밖으로 나가거나 / 첫 방문이 아니거나 / 도착지점이 공사지점인데 도착시간이 공사시작 시간보다 같거나 큰 경우우
is_ban = False
if (not inside(nax,nay)) or (not first(nax,nay,nd,a+1)) or ((arr[nay][nax] and nt >= arr[nay][nax])):
is_ban = True
# 도착지점까지 갈 수 있는지 확인하기
if not is_ban:
for i in range(1,a+1):
nx,ny = x+dx*i,y+dy*i
# 중간 지점이 시점 nt에 공사중이어도 괜찮다.
if arr[ny][nx] and nt > arr[ny][nx]:
is_ban = True
break
# 불가능한 경우 다른 방향 탐색하기
if is_ban:
continue
# 가능한 경우 큐에 넣기
nx,ny = x+dx*(a+1),y+dy*(a+1)
Q.append((nx,ny,nd,a+1))
V[a+1][nd][ny][nx] = nt
else:
# 방향을 바꾸는 경우 항상 가속도가 1인 상태로 큐에 넣는다.
nx,ny = x+dx,y+dy
if inside(nx,ny) and first(nx,ny,nd,1) and ((not arr[ny][nx]) or (arr[ny][nx] and nt < arr[ny][nx])):
Q.append((nx,ny,nd,1))
V[1][nd][ny][nx] = nt
# 도달한 경우 중 가장 작은 케이스 출력하기
answer = [V[a][d][-1][-1] for a in range(accel) for d in range(4) if V[a][d][-1][-1] != -1]
print('Fired' if not answer else min(answer))
테케 받아서 BFS 돌리기
자바
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] arr;
static int[][][][] V;
static int[][] dire = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
static final int accel = 16;
static boolean inside(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < N;
}
static boolean first(int x, int y, int d, int a) {
return V[a][d][y][x] == -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
V = new int[accel][4][N][N];
for (int a = 0; a < accel; a++)
for (int d = 0; d < 4; d++)
for (int i = 0; i < N; i++)
Arrays.fill(V[a][d][i], -1);
ArrayDeque<int[]> Q = new ArrayDeque<>();
for (int nd = 0; nd < 2; nd++) {
Q.offer(new int[] { 0, 0, nd, 0 });
V[0][nd][0][0] = 0;
}
while (!Q.isEmpty()) {
int[] cur = Q.poll();
int x = cur[0], y = cur[1], d = cur[2], a = cur[3];
int nt = V[a][d][y][x] + 1;
for (int nd = 0; nd < 4; nd++) {
int dx = dire[nd][0], dy = dire[nd][1];
if (nd == d) {
int nax = x + dx * (a + 1), nay = y + dy * (a + 1);
boolean isBan = false;
if (!inside(nax, nay) || !first(nax, nay, nd, a + 1)
|| (arr[nay][nax] > 0 && nt >= arr[nay][nax])) {
isBan = true;
}
if (!isBan) {
for (int i = 1; i <= a + 1; i++) {
int nx = x + dx * i, ny = y + dy * i;
if (arr[ny][nx] > 0 && nt > arr[ny][nx]) {
isBan = true;
break;
}
}
}
if (isBan)
continue;
Q.offer(new int[] { nax, nay, nd, a + 1 });
V[a + 1][nd][nay][nax] = nt;
} else {
int nx = x + dx, ny = y + dy;
if (inside(nx, ny) && first(nx, ny, nd, 1)
&& (arr[ny][nx] == 0 || (arr[ny][nx] > 0 && nt < arr[ny][nx]))) {
Q.offer(new int[] { nx, ny, nd, 1 });
V[1][nd][ny][nx] = nt;
}
}
}
}
int answer = Integer.MAX_VALUE;
for (int a = 0; a < accel; a++) {
for (int d = 0; d < 4; d++) {
if (V[a][d][N - 1][N - 1] != -1) {
answer = Math.min(answer, V[a][d][N - 1][N - 1]);
}
}
}
System.out.print(answer == Integer.MAX_VALUE ? "Fired" : answer);
}
}
다차원 배열 초기화에서는 내부 1중 배열만 남을 때 까지 접근을 해서 Arrays.fill을 사용한다.
공통 변수들은 메인함수 말고 클래스에 static으로 정의해서 문제풀기.
함수 전달할때 파라미터를 계속 넘겨줘야한다.
자바로 풀 때, 전체적인 흐름들은 맞는데 메서드가 익숙하지 않거나 괄호나 세미콜론 등 자잘한 오류들이 발생.
댓글