백준 17070 파이프 옮기기 1 (Gold 5)

전략

• DFS식 접근
  
  • 각 파이프 모드마다 갈 수 있는 경우의 수를 자료구조에 저장해둔다.
  • DFS를 하면서 파이프를 놓을 수 있는지 확인한다
  • 만약 다음에 놓을 파이프의 위치가 (N,N)이면 경로수 ++를 해준다

• DP식 접근
  

  • 자신의 파이프로 들어오는 1,2,3 mode의 파이프를 dp로 기억해두고, 다음 DP를 업데이트 할 때 가능한 Pipe mode가 나올 수 있던 이전 pipe mode의 dp값을 지금 pipe mode가 1일 때 첫번째 DP값으로, 2번이면 두번째 DP값으로 업데이트 한다.
  • 각각의 파이프 모드를 저장해나가다가 마지막 N,N에 도착하는 모든 모드의 파이프 경우의 수를 다 더해주면 정답이된다

• 결과 비교
  

  • 두 방식을 비교했을 때 DP방식으로 풀었을 때 DFS를 사용하는 것 보다 약 5배 정도 더 빠름을 알 수 있다. 경로 관련 DFS일 때 시간초과가 발생하면 DP를 의심하자

정답코드

• DFS

package SamsungSwTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;


public class MovePipeDFS {
	static int N;
	static int[][] Room;
	static int[] dx = { 0, 1, 1 };
	static int[] dy = { 1, 1, 0 };
	static int result = 0;
	static ArrayList<Integer>Mode[]; 
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Room = new int[N][N];


		for (int i = 0; i < N; i++) {
			String in[] = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				Room[i][j] = Integer.parseInt(in[j]);
			}
		}
		
		Mode = new ArrayList[3];
		
		for(int i = 0; i < 3; i++) {
			Mode[i] = new ArrayList<Integer>();
		}
		
		//초기화 
		Mode[0].add(0);
		Mode[0].add(1);
		
		Mode[1].add(0);
		Mode[1].add(1);
		Mode[1].add(2);
		
		Mode[2].add(1);
		Mode[2].add(2);
		
		DFS(0,1,0);
		DFS(0,1,1);
		
		System.out.println(result);
	}
	
	public static void DFS(int x, int y, int mode) {
	
		int nx = x + dx[mode];
		int ny = y + dy[mode];
		
		
		if(nx<0||nx>=N||ny<0||ny>=N||Room[nx][ny]==1)return;
		

		for(int i = 0; i < Mode[mode].size(); i++) {
			if(mode == 1) {
				if(Room[x+1][y] == 1 ||Room[x][y+1]==1)return;
			}
			
			if(nx == N-1 && ny == N-1) {
				result++;
				return;
			}
			
			DFS(nx,ny,Mode[mode].get(i));
		}
		
	}
	
}

• DP

package SamsungSwTest;

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

public class MovePipeDP {
	static int N;
	static int[][] Room;
	static int[][][] DP;
	static ArrayList<Integer>[] Mode;
	static int[] dx = { 0, 1, 1 };
	static int[] dy = { 1, 1, 0 };
	static int result = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Room = new int[N][N];
		DP = new int[N+1][N+1][3];

		for (int i = 0; i < N; i++) {
			String in[] = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				Room[i][j] = Integer.parseInt(in[j]);
			}
		}

		putPipe();
		
		for(int i = 0; i < 3; i++) {
			result += DP[N-1][N-1][i];
		}
		System.out.println(result);
	}

	public static void putPipe() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				
				//초깃값 세팅
				if(i == 0 && j == 0) {
					DP[0][1][0] = 1;
					DP[0][1][1] = 0;
					DP[0][1][2] = 0;
					continue;
				}
				
				if(Room[i][j] == 1) {
					DP[i][j][0] = 0;
					DP[i][j][1] = 0;
					DP[i][j][2] = 0;
				}
				
				// 현재칸으로 오는 mode들에 대해서 유효성 검사
				for (int k = 0; k < 3; k++) {
					int mode = k;
					// 왼쪽, 대각선,위쪽 검사하기
					int temp0 = 0; // 0번 mode dp
					int temp1 = 0; // 1번 mode dp
					int temp2 = 0; // 2번 mode dp

					if (mode == 0) {
						if((j+1>=N)||Room[i][j+1]==1)continue;			
						temp0 = DP[i][j][0];
						temp1 = DP[i][j][1];
						DP[i][j+1][0] += (temp0 + temp1);
					}

					// 대각선 검사
					if (mode == 1) {
						if((i+1>=N)||(j+1>=N) || Room[i][j+1]==1||Room[i+1][j]==1|| Room[i+1][j+1]==1)continue;
						
						temp0 = DP[i][j][0];
						temp1 = DP[i][j][1];
						temp2 = DP[i][j][2];
						
						// 1번 파이프를 타고왔으면 모두 가능하니까 다 더해준다
						DP[i+1][j+1][1] += (temp0 + temp1 + temp2);
					}

					if (mode == 2) {
						if((i+1>=N)||Room[i+1][j]==1)continue;
						// 위쪽 검사
						temp1 = DP[i][j][1];
						temp2 = DP[i][j][2];

						// 2번 파이프를 타고 왔으니 0번 파이프 빼고 더해준다
						DP[i+1][j][2] += (temp1 + temp2);
					}
				}
			}
		}

	}

}