문제 풀이 날짜: 2025-09-03
💡Github URL
💡분류
다이나믹 프로그래밍, 그래프 이론, 그래프 탐색
💡알고리즘 설계
3차원 배열 int[][][] mem에 각 지점에 특정 상태로 도달하는 방법의 가짓수를 저장(메모이제이션), 이후 그 지점에서 다시 전파할 때 그 가짓수를 다음 도달 지점에도 전달하여 업데이트.
이 때, 순회 방법은 문제 조건 상 반드시 상→하, 좌→우로만 이동해야 하기 때문에 일반적인 2차원 배열 순회 방식처럼 상→하, 좌→우로 순회하면 각 지점에 도달하는 모든 가짓수가 업데이트 되고 난 뒤, 다음 전파를 진행할 수 있음.
💡코드
메모리: 14380 KB, 시간: 108 ms
import java.util.*;
import java.io.*;
/*
pipe위치: (y, x)
pipe의 상태: 0(가로), 1(세로), 2(대각선)
-> 각 상태별로 움직일 수 있는 동작이 다름
0(가로): dist[0], dist[2] 가능
1(세로): dist[0], dist[1] 가능
2(세로): dist[0], dist[1], dist[2] 가능
그냥 하드코딩 하는게 나려나?
움직이는 동작: dist[0](가로), dist[1], dist[2]
dist[0]: (y, x+1)이 빈 칸
dist[1]: (y+1, x)가 빈 칸
dist[2]: (y, x+1), (y+1, x), (y+1, x+1)이 빈 칸
*/
public class Main {
static int N;
static int[][] map;
static long[][][] mem;
static void moveH(int bY, int bX, int fY, int fX, int s) {
if (fX + 1 < N && map[fY][fX + 1] == 0) {
mem[fY][fX + 1][0] += mem[fY][fX][s];
}
}
static void moveV(int bY, int bX, int fY, int fX, int s) {
if (fY + 1 < N && map[fY + 1][fX] == 0) {
mem[fY + 1][fX][1] += mem[fY][fX][s];
}
}
static void moveD(int bY, int bX, int fY, int fX, int s) {
if (fY + 1 < N && fX + 1 < N &&
map[fY][fX + 1] == 0 && map[fY + 1][fX] == 0 && map[fY + 1][fX + 1] == 0) {
mem[fY + 1][fX + 1][2] += mem[fY][fX][s];
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
mem = new long[N][N][3];
mem[0][1][0] = 1;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) map[i][j] = Integer.parseInt(st.nextToken());
}
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (map[y][x] == 1) continue;
if (mem[y][x][0] > 0) { // 가로로 (y,x)에 도착
moveH(0,0,y,x,0);
moveD(0,0,y,x,0);
}
if (mem[y][x][1] > 0) { // 세로로 (y,x)에 도착
moveV(0,0,y,x,1);
moveD(0,0,y,x,1);
}
if (mem[y][x][2] > 0) { // 대각으로 (y,x)에 도착
moveH(0,0,y,x,2);
moveV(0,0,y,x,2);
moveD(0,0,y,x,2);
}
}
}
long ans = mem[N-1][N-1][0] + mem[N-1][N-1][1] + mem[N-1][N-1][2];
System.out.println(ans);
}
}💡시간복잡도
O(N^2)
2차원 배열 전체 순회
💡틀린 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[][] map;
static int[][][] mem;
static ArrayDeque<int[]> q;
static void moveH(int bY, int bX, int fY, int fX, int s) {
if(fX + 1 < N && map[fY][fX+1] == 0) {
int cnt = mem[fY][fX][s];
if(mem[fY][fX+1][0] != 0) {
mem[fY][fX+1][0] += cnt;
}
else {
mem[fY][fX+1][0] += cnt;
q.offerLast(new int[] {bY, bX+1, fY, fX+1, 0});
}
}
return;
}
static void moveV(int bY, int bX, int fY, int fX, int s) {
if(fY + 1 < N && map[fY+1][fX] == 0) {
int cnt = mem[fY][fX][s];
if(mem[fY+1][fX][1] != 0) {
mem[fY+1][fX][1] += cnt;
}
else {
mem[fY+1][fX][1] += cnt;
q.offerLast(new int[] {bY+1, bX, fY+1, fX, 1});
}
}
return;
}
static void moveD(int bY, int bX, int fY, int fX, int s) {
if(fY + 1 < N && fX + 1 < N && map[fY+1][fX] == 0 && map[fY][fX+1] == 0 && map[fY+1][fX+1] == 0) {
int cnt = mem[fY][fX][s];
if(mem[fY+1][fX+1][2] != 0) {
mem[fY+1][fX+1][2] += cnt;
}
else {
mem[fY+1][fX+1][2] += cnt;
q.offerLast(new int[] {bY+1, bX+1, fY+1, fX+1, 2});
}
}
return;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
mem = new int[N][N][3];
mem[0][1][0] = 1;
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
q = new ArrayDeque<>();
q.offerLast(new int[] {0, 0, 0, 1, 0}); // [ backY, backX, frontX, frontY, state]
while(!q.isEmpty()) {
int[] tmp = q.pollFirst();
int bY = tmp[0]; int bX = tmp[1]; int fY = tmp[2]; int fX = tmp[3]; int s = tmp[4];
if(fY == N-1 && fX == N-1) {continue;}
switch(s) {
case(0):
moveH(bY, bX, fY, fX, s);
moveD(bY, bX, fY, fX, s);
break;
case(1):
moveV(bY, bX, fY, fX, s);
moveD(bY, bX, fY, fX, s);
break;
case(2):
moveH(bY, bX, fY, fX, s);
moveV(bY, bX, fY, fX, s);
moveD(bY, bX, fY, fX, s);
break;
}
}
System.out.println(mem[N-1][N-1][0] + mem[N-1][N-1][1] + mem[N-1][N-1][2]);
}
}queue를 사용해서 BFS에 메모이제이션을 추가하는 방식을 시도해봤으나, 틀림.
메모이제이션을 통해 특정 지점에 도달했을 경우, 이미 도달한 적이 있으면(mem[y][x][n] > 0), 이미 queue 내부에 그 지점에서 전파되는 항목들이 들어있기 때문에 mem[y][x][n]만 업데이트 하고 queue에는 추가하지 않는 로직을 짜려고 했으나, 상황에 따라 나중에 추가되는 가짓수가 업데이트에 반영되지 않고 업데이트가 이미 진행되는 경우가 발생할 수 있기 때문에 틀림.
💡 기억할정보
queue를 사용하더라도, '반드시 순서대로' 업데이트 되는 것은 아니라는 걸 기억. (자주 틀리는 듯)
개발자 지망생