[백준] 10164 격자상의 경로 - 동적계획법(Dynamic Programming, DP) JAVA

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

10164번: 격자상의 경로

코드설명

DP 문제입니다.

 

이 문제의 핵심은, (1,1) ~ (K번째)의 위치로 가는 방법 x (K번째)의 위치 ~ (N, M) 으로 K번째 위치를 반드시 거치면서 경로를 만든다는 것입니다.

이 문제의 경우 (1,1)에서 (N,M)으로 무조건 이동하는 방향인 우하향하므로 2중 for문을 순회해도 문제가 없습니다.

 

제가 처음에 푼 코드는 위의 로직을 그대로 구현했습니다.

 

하지만, 조금 더 손쉽게 푸는 방법은, (1,1)에서 (K번쨰위치) 의 위치를 구하는 방법은 

int x = (k) / m;
int y = (k) % m;

위의 식을 통해 K번쨰 위치인 
(1, 1) ~ (x, y)
(1, 1) ~ (N - x + 1, M - y + 1) 이 값을 구할경우 손쉽게 구할 수 있습니다.

행의 시작과 열의 시작을 1로 할때

위와 같이 k번째의 행은 ( K )/ M 입니다.

k번쨰의 열은 ( K ) % M 입니다.

 

위의 식을 활용할경우 1개의 함수로 (1,1)에서 각 독립된 경로를 구하고 그것들을 곱해줌으로써 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int K, N, M, idx = 1;
	public static int[][] dp = new int[16][16];
	public static int[] dx= {1,0};
	public static int[] dy = {0,1};
	public static int answer = 0, firstWay= 0, secondWay = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	dp[1][1] = 1;
    	int cnt = 0;
    	int tempI = 0;
    	int tempJ = 0;
    	// (1,1)에서 K번이 위치한 곳까지. K점을 도착하는 숫자를 구한다.
    	for(int i=1; i<=N;i++) {
    		for(int j=1; j<=M;j++) {
    			cnt+=1;
    			if(cnt == K ) {
    				tempI = i;
    				tempJ = j;
    			}
    			if(cnt > K && K > 0) {
    				break;
    			}
    			
    			int nr = i;
    			int nc = j;
    			for(int dir=0;dir<2;dir++) {
    				nr = i - dx[dir];
        			nc = j - dy[dir];
    				if(nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
    					dp[i][j] += dp[nr][nc]; 
    				}
    			}
    		}
    		if(cnt > K && K > 0) {
    			break;
    		}
    		

    	}
    	firstWay = dp[tempI][tempJ]; 
    	answer = dp[N][M];
    	
    	for(int i=1; i<=N;i++) {
    		for(int j=1; j<=M;j++) {
    			dp[i][j] = 0;
    		}
    	}
    	dp[tempI][tempJ] = 1;
    	for(int i=tempI; i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			int nr = i;
    			int nc = j;
    			for(int dir=0;dir<2;dir++) {
    				nr = i - dx[dir];
        			nc = j - dy[dir];
    				if(nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
    					dp[i][j] += dp[nr][nc]; 
    				}
    			}
    		}
    	}
    	secondWay = dp[N][M];
    	
    	if(K > 0) {
    		System.out.println(firstWay * secondWay);	
    	}
    	else {
    		System.out.println(answer);
    	}
    }
}

 

 

 

처음에 풀었을때 코드입니다.

단순하게 생각해서, 최대 N 15, M 15 이기에 시간복잡도가 O(NM) 이라고 생각했지만, 잘못된 생각이었습니다.

이유는, BFS가 따로 방문처리를 하지 않기 떄문에, 약 2가지의 선택지로 시간복잡도는 O( 2^(NM)) 입니다. 

당연히 시간초과가 발생합니다. 백준 제출시에는 33점에서 틀립니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] map;
	static int[][] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N; i++)
			Arrays.fill(cache[i], -1);
		
		for(int i=0,idx = 1; i<N; i++) {
			for(int j=0;j<M; j++) {
				map[i][j] = idx++;
			}
		}
		
		if(K == 0) {
			System.out.println((long)BFS(0, 0, N-1, M-1));
		}
		else {
			System.out.println( (long) BFS(0, 0, (K-1) / M, (K-1) % M) * (long) BFS( (K-1) / M, (K-1) % M, N-1, M-1));
			
		}
		
	}
	
	
	static long BFS(int r, int c, int targetR, int targetC) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {r, c});
		int[] dx = {1, 0};
		int[] dy = {0, 1};
		long wayCnt = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			if(temp[0] == targetR && temp[1] == targetC) {
				wayCnt += 1;
				continue;
			}
			for(int dir = 0; dir < 2; dir++) {
				int nr = temp[0] + dx[dir];
				int nc = temp[1] + dy[dir];
				if(nr < 0 || nr >= targetR + 1 || nc < 0 || nc >= targetC + 1) {
					continue;
				}
				q.offer(new int[] {nr, nc});
			}
		}
		
		return wayCnt;
	}
	
}

 

메모이제이션을 활용하여 개선시켜보겠습니다.

DFS와 메모이제이션을 활용하여 시간복잡도는 O(N*M)이 됩니다.

이전에 2가지 선택을 모두 진행하던 것( O(2^(N*M))과 상반됩니다. 

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] map;
	static int[][] cache;
	static int[] dx = {1, 0};
	static int[] dy = {0, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N; i++)
			Arrays.fill(cache[i], -1);
		
		for(int i=0,idx = 1; i<N; i++) {
			for(int j=0;j<M; j++) {
				map[i][j] = idx++;
			}
		}
		
		if(K == 0) {
			System.out.println( DFS(0, 0, N-1, M-1));
		}
		else {
			System.out.println( DFS(0, 0, (K-1) / M, (K-1) % M) * DFS( (K-1) / M, (K-1) % M, N-1, M-1));
			
		}
		
	}
	
	static int DFS(int r, int c, int targetR, int targetC) {
		if(r == targetR && c == targetC) {
			return 1;
		}
		
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		for(int dir = 0; dir < 2; dir ++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= targetR + 1 || nc < 0 || nc >= targetC + 1) {
				continue;
			}
			ret += DFS(nr, nc, targetR, targetC);
		}
		return cache[r][c] = ret; 
	}
	
	
}