백준 17070 파이프 옮기기 1

1. 문제 링크

17070번: 파이프 옮기기 1

 

2. 문제 및 입출력예제

 

3. 문제 풀이

하나씩 움직여보는 풀이와 dp 풀이가 있다.

첫번째 방식은 메모리는 402,508KB, 시간은 880ms 가 나온다.

두번째 방식은 메모리는 11,564KB, 시간은 76ms가 나온다.

확실히 dp가 성능 면에서 우수하다.

 

4. 코드

1) 구현, 시뮬레이션

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
	static int[] dx = {0,1,1}, dy= {1,0,1};
	static int N, dp[][], count;
	static boolean[][] map;
	static Queue<int[]> queue;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new boolean[N][N];
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				if(split[j].equals("0")) {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			}
		}
		dp = new int[N+1][N+1];
		count = 0;
		queue = new ArrayDeque<>();
		queue.offer(new int[] {0, 1, 0});
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			switch (now[2]) {
			case 0:
				check(move(now, 0));
				check(move2(now));
				break;
			case 1:
				check(move(now, 1));
				check(move2(now));
				break;
			case 2:
				check(move(now, 0));
				check(move(now, 1));
				check(move2(now));
				break;
			}
		}
		System.out.println(count);
	}
	private static void check(int[] temp) {
		if(temp!= null) {
			if(temp[0]==N-1 && temp[1]== N-1) {
				count++;
			}
			else {
				queue.offer(temp);
			}
		}
	}
	private static int[] move2(int[] now) {
		int X = now[0];
		int Y = now[1];
		if(X+1>=N || Y+1>=N) {
			return null;
		}
		if(map[X+1][Y] && map[X+1][Y+1] && map[X][Y+1]) {
			return new int[] {X+1, Y+1, 2};
		}
		return null;
	}
	private static int[] move(int[] now, int dir) {
		int X = now[0]+dx[dir];
		int Y = now[1]+dy[dir];
		if(X>=N || Y>=N || !map[X][Y]) {
			return null;
		}
		dp[X][Y]++;
		return new int[] {X, Y, dir};
	}
}

 

2) dp

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean[][] map = new boolean[N+1][N+1]; //조금 더 최적화
		for(int i=1;i<N+1;i++) {
			String[] split = br.readLine().split(" ");
			for(int j=1;j<N+1;j++) {
				if(split[j-1].equals("0")) {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			}
		}
		
		int[][][] dp = new int[N+1][N+1][3]; //0(가로), 1(대각선), 2(아래)
		dp[1][2][0] = 1;
		for(int i=1;i<N+1;i++) {
			for(int j=3;j<N+1;j++) {
				if(!map[i][j]) continue;
				//앞과 이어 가로로 둘 경우
				dp[i][j][0] = dp[i][j-1][0]+dp[i][j-1][1];
				
				if(i==1) continue; //이것까지 하면 조금 더 최적화
				//앞과 이어 세로로 둘 경우
				dp[i][j][2] = dp[i-1][j][1]+dp[i-1][j][2];
				
				//앞과 이어 대각선으로 둘 경우
				if(!map[i-1][j] || !map[i][j-1]) {
					continue;
				}
				dp[i][j][1] = dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2];
			}
		}
		System.out.println(dp[N][N][0]+dp[N][N][1]+dp[N][N][2]);
	}
}