[백준] 17070번 : 파이프 옮기기 1 - 자바[Java]

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

17070번: 파이프 옮기기 1

 

풀이

먼저 파이프가 놓여 있는 위치를 ArrayList<Point> pipe에 저장하고, 놓여있는 방향은 dir에 저장한다.

(0 = 가로, 1 = 세로, 2 = 대각선)

그 다음 재귀함수를 호출하여 모든 경우의 수를 탐색한다.

    	ArrayList<Point> pipe = new ArrayList<>();
    	pipe.add(new Point(0,0));
    	pipe.add(new Point(0,1));
    	
    	move(pipe, 0);

코드(재귀함수)

import java.io.*;
import java.util.*;

public class Main {
	
	static int[][] arr;
	static int n, cnt = 0;
	
	static class Point {
		int r;
		int c;
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
    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());
    		}
    	}
    	
    	ArrayList<Point> pipe = new ArrayList<>();
    	pipe.add(new Point(0,0));
    	pipe.add(new Point(0,1));
    	
    	move(pipe, 0);
    	
    	System.out.println(cnt);
    }
    
    public static void move(ArrayList<Point> pipe, int dir) {
    	Point cur = pipe.get(1);
    	
    	// 이동 완료한 경우
    	if (cur.r == n-1 && cur.c == n-1) {
    		cnt++;
    		return;
    	}
    	
    	// 가로 방향
    	if (dir == 0) {
    		// 가로로 이동
    		int nr = cur.r;
    		int nc = cur.c + 1;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 0);
    		}
    		
    		// 대각선으로 이동
    		nr = cur.r + 1;
    		nc = cur.c + 1;
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0 && arr[nr-1][nc] == 0 && arr[nr][nc-1] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 2);
    		}
    	}
    	// 세로 방향
    	else if (dir == 1) {
    		// 세로로 이동
    		int nr = cur.r + 1;
    		int nc = cur.c;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 1);
    		}
    		
    		// 대각선으로 이동
    		nr = cur.r + 1;
    		nc = cur.c + 1;
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0 && arr[nr-1][nc] == 0 && arr[nr][nc-1] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 2);
    		}
    	}
    	// 대각선 방향
    	else if (dir == 2) {
    		// 가로로 이동
    		int nr = cur.r;
    		int nc = cur.c + 1;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 0);
    		}
    		
    		// 세로로 이동
    		nr = cur.r + 1;
    		nc = cur.c;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 1);
    		}
    		
    		// 대각선으로 이동
    		nr = cur.r + 1;
    		nc = cur.c + 1;
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0 && arr[nr-1][nc] == 0 && arr[nr][nc-1] == 0) {
    			ArrayList<Point> newPipe = new ArrayList<>(pipe);
    			newPipe.remove(0);
    			newPipe.add(new Point(nr, nc));
    			
    			move(newPipe, 2);
    		}
    	}
    }
    
    public static boolean checkIndex(int r, int c) {
    	return r >= 0 && r < n && c >= 0 && c < n;
    }
    
}

 

개선한 풀이

- move() 함수에서 모든 방향에서 대각선으로 이동 가능하므로 대각선 이동은 공통적으로 수행한다.

- ArrayList<Point> pipe의 위치를 따로 저장할 필요 없이 한 위치만 필요하므로 위치를 넘겨준다.

import java.io.*;
import java.util.*;

public class Main {
	
	static int[][] arr;
	static int n, cnt = 0;
	
    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());
    		}
    	}
    	
    	move(0, 1, 0);
    	
    	System.out.println(cnt);
    }
    
    public static void move(int r, int c, int dir) {
    	
    	// 이동 완료한 경우
    	if (r == n-1 && c == n-1) {
    		cnt++;
    		return;
    	}
    	
    	// 가로 방향
    	if (dir == 0) {
    		// 가로로 이동
    		int nr = r;
    		int nc = c + 1;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			move(nr, nc, 0);
    		}
    	}
    	// 세로 방향
    	else if (dir == 1) {
    		// 세로로 이동
    		int nr = r + 1;
    		int nc = c;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			move(nr, nc, 1);
    		}
    	}
    	// 대각선 방향
    	else if (dir == 2) {
    		// 가로로 이동
    		int nr = r;
    		int nc = c + 1;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			move(nr, nc, 0);
    		}
    		
    		// 세로로 이동
    		nr = r + 1;
    		nc = c;
    		
    		if (checkIndex(nr, nc) && arr[nr][nc] == 0) {
    			move(nr, nc, 1);
    		}
    	}
    	
    	// 모든 방향은 대각선으로 이동
		int nr = r + 1;
		int nc = c + 1;
		if (checkIndex(nr, nc) && arr[nr][nc] == 0 && arr[nr-1][nc] == 0 && arr[nr][nc-1] == 0) {
			move(nr, nc, 2);
		}
    }
    
    public static boolean checkIndex(int r, int c) {
    	return r >= 0 && r < n && c >= 0 && c < n;
    }
    
}

 

DP를 사용한 풀이

DP를 사용하여 각각 위치마다 도달할 수 있는 경우의 수를 저장한다. 이 때 3가지 방향이 따로 존재하므로 3차원 dp 배열을 생성한다.

import java.io.*;
import java.util.*;

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());
    	int[][] 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());
    		}
    	}
    	
    	int[][][] dp = new int[n][n][3]; // 0은 가로, 1은 세로, 2는 대각선
    	dp[0][1][0] = 1; // 처음에는 (0,1)에서 가로 방향으로 놓여있음
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 2; j < n; j++) {
    			if (arr[i][j] == 1) continue;
    			
    			if (j-1 >= 0) {
    				dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2];
    			}
    			if (i-1 >= 0) {
    				dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];
    			}
    			if (i-1 >= 0 && j-1 >= 0 && arr[i-1][j] == 0 && arr[i][j-1] == 0) {
    				dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
    			}
    		}
    	}
    	
    	System.out.println(dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2]);
    }
    
}

주의할 점은 2중 for문을 수행할 때 j=2부터 시작한다는 점이다.
2부터 시작하지 않고 0부터 시작하면 dp[0][1][0]이 0으로 초기화되므로 틀린 답이 나온다.
j=0부터 시작하고 싶으면 dp[i][j][0] += dp[i][j-1][0] + dp[i][j-1][2]; 으로 바꿔야 한다.

 

참고

• https://codeung.tistory.com/248

풀이 비교

DP를 사용한 풀이

재귀함수를 사용한 개선된 풀이, 재귀함수를 사용한 원래 풀이