[Java Algorithm] 파이프 옮기기 1 BOJ #17070

문제

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

17070번: 파이프 옮기기 1

 

내 문제 풀이

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

public class Main {

	static int n;
	static int memory[][];
	
	// 가로, 세로, 대각 순서대로 탐색
	static int[] dx = {0, 1, 1};
	static int[] dy = {1, 0, 1};
	
	public static void move(int x, int y, int type) {
		if(type == 0 || type == 1) { // 가로 or 세로
			for(int i = 0; i < 2; i++) {
				int j = type; // 가로일 때는 가로, 세로일 때는 세로를 탐색
				if(i == 1) j = 2; // 가로, 세로 모두 대각선 탐색 필요
				
				int nx = x + dx[j];
				int ny = y + dy[j];
				if(check(nx, ny, j)) {
					memory[nx][ny] += 1; // 경우의 수 누적
					move(nx, ny, j); // 탐색할 x, y 좌표와 새롭게 나아갈 파이프의 타입
				}
			}
		} else if(type == 2) { // 대각
			for(int i = 0; i < 3; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(check(nx, ny, i)) {
					memory[nx][ny] += 1; // 경우의 수 누적
					move(nx, ny, i); // 탐색할 x, y 좌표와 새롭게 나아갈 파이프의 타입
				}
			}
		}
	}
	
	public static boolean check(int x, int y, int type) {
		if(x < 0 || y < 0 || x >= n || y >= n || memory[x][y] == -1) { // 범위를 벗어나거나, 벽일 때
			return false;
		} 
		if(type == 2 && (memory[x-1][y] == -1 || memory[x][y-1] == -1)) { // 대각선일 때는 나아갈 방향 뿐만 아니라 아래, 오른쪽도 모두 비어있어야 함
			return false;
		}
		return true;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(in.readLine());
		memory = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < n; j++) {
				int now = Integer.parseInt(st.nextToken());
				if(now == 1) {
					memory[i][j] = -1;
				}
			}
		}
		
		if(memory[n-1][n-1] == -1) {
			System.out.println(0);
		} else {
			memory[0][0] = 1;
			memory[0][1] = 1;
			move(0, 1, 0); // x, y좌표, 파이프 type
			System.out.println(memory[n-1][n-1]);
		}
	}
}

👉 DP 문제

• 경우의 수를 memoization하기 위해 memory 배열을 만들고, 벽이 있을 때는 -1을 넣어 구별했다.
• 파이프의 목적지인 (n-1, n-1)에 벽이 있을 경우 절대 갈 수 없으므로, 바로 0을 출력하며 종료했다.
• 그 외의 경우에는 memory의 (0, 0), (0, 1)을 1로 바꿔주어 시작점에 해당하는 경우의 수를 넣고,
  move 메소드를 실행하여 memoization 재귀를 진행했다.
• move는 다음 파이프라인의 시작점이 될 x, y 좌표와 파이프라인의 type에 대한 정보를 파라미터로 한다.
  type은 파이프의 방향값으로, 나는 가로, 세로, 대각선을 각각 0, 1, 2로 표현했다.
• move는 재귀로 구현해주었는데, 메소드를 크게 가로 or 세로일 때와 대각선일 때로 나누었다.
  (대각선일때는 총 세 곳을 탐색해야 하며, 가로 or 세로일 때는 두 곳을 탐색해야 하기 때문)
• 우선 가로 or 세로일 때는, for문을 이용하여 2번 반복하도록 했는데,
  for문 안에서 j라는 변수를 만들어서 type에 대한 정보를 담았다.
• 나는 dx, dy 배열을 만들어서 주변 탐색을 용이하게 했는데,
  type이 0, 1, 2 숫자 순서대로 가로, 세로, 대각선을 의미하도록 한 것을 이용하여
  dx, dy 배열 또한 type의 값에 맞춰 순서대로 가로, 세로, 대각선 탐색을 할 수 있게 했다.
• type에 맞춰 check 메소드를 이용하여 적절한지를 판단하고, 적절하다고 판단되면
  경우의 수를 누적하고, move를 재귀호출하여 다음 탐색을 진행할 수 있도록 했다.
• memory 배열의 (n-1, n-1)에 저장된 경우의 수를 결과로 출력했다.

 

💡 피드백

• 재귀로 돌리니까 시간이 많이 소요되었다. 다른 풀이 방법도 생각해봐야겠다.
  👉 https://seolhee2750.tistory.com/256 해결 완료!