[백준 17070] 파이프 옮기기 1 (JAVA)

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

17070번: 파이프 옮기기 1

 

이번 포스팅에서는 삼성 A형 기출문제인 파이프 옮기기 1 문제를 다뤄보도록하겠다.

 

먼저 문제 분석을 하자면 N*N 크기의 행렬 시작점 (0,1) 에서 종점 (n,n) 까지 도달가능한 모든 경우의 수를

찾는 문제로 이동가능한 방향은 가로, 세로, 대각 세가지 방향으로만 진행이 가능하며

벽이 존재하기 때문에 벽에 막혀 진행하지 못하는 경우는 제외해주어야 한다.

 

이때 대각 방향으로 이동할때는 가로,세로,대각 모두 벽이 존재해서는 안된다.

 

그간 다뤄왔던 다른 완전 탐색문제들처럼 최단경로를 찾는것이 아닌 모든 경우의 수를 찾는 문제이므로

DFS를 사용해 접근하도록 하겠다.

 

현재 파이프에 따라 가능한 이동방향이 다르므로 조건에 따라 재귀호출해줄수 있는 DFS가 조금 더

적절한 풀이방법이라 생각한다.

 

먼저 재귀호출을 할 분기점에 대해 정리하자면

현재 파이프의 방향이 가로인 경우) 가로, 대각으로 이동가능

현재 파이프의 방향이 세로인 경우) 세로, 대각으로 이동가능

현재 파이프의 방향이 대각인 경우) 가로 세로, 대각으로 이동가능

 

그리고 리턴되는 시점은 범위를 벗어나거나, 혹은 종점에 도달했을 경우가 될것이다.

 

그럼 바로 코드로 풀이해 보도록 하겠다.

 

먼저 필드로 벽의 정보를 받을 행렬, 그리고 n의 값, 경우의 수를 카운트할 값을 선언해두겠다.

 

class BOJ17070Sol {
	
	private boolean[][] metrix;
	private int n,ans;
}

 

 

다음으로는 n의 값을 입력받았다면 배열의 길이를 동적으로 할당해줄 메소드를 하나 만들어준다.

 

	private void setMetrix() { metrix = new boolean[n][n]; }

 

 

이제 입력부를 만들어 주도록하겠다. 입력 형식에 맞춰 순차적으로

n의 값을 받고, 행렬의 정보를 받는다.

이때 행렬의 값이 1인 경우에만 true 값을 저장해주어 구분해주었다.

 

	private void init() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(in.readLine());
		setMetrix();
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j = 0; j < n; j++) {
				if(st.nextToken().equals("1")) { metrix[i][j] = true; }
			}
		}
		in.close();
	}

 

그리고 이 init 메소드를 생성자안에 넣어 객체를 생성할때 자동으로 입력을 받은상태가

될 수 있도록 만들어 주었다.

 

	BOJ17070Sol() {
		try {
			init();			
		}catch (IOException e){
			e.printStackTrace();
		}
	}

 

 

이제 종점에 도달할수 없는 한가지 예외 상황에 대해 처리해주기 위한

endChk 메소드를 만들어준다. 종점이 벽이라면 절대 도달할수 없으므로 탐색자체를 시작할 필요가 없다.

 

	private boolean endChk() {
		return metrix[n - 1][n - 1];
	}

 

 

이제 탐색의 핵심인 DFS를 구현한 메소드이다.

인자로 파이프의 방향, 행렬의 좌표를 전달하여 조건에 따라 재귀호출해줄수 있도록 했다.

조건분기는 위에서 언급한 상황과 동일하다.

이때 인덱스범위에 대한 예외처리만 별도로 조건문에 추가해주었다.

 

	private void dfs(Boolean way,int x, int y) {
		if(x == n - 1 && y == n - 1) {
			ans++;
			return;
		}
		if(x == n || y == n || metrix[x][y]) { return; }
		
		if(way == null || way) { dfs(true, x + 1, y); }
		if(way == null || !way){ dfs(false, x, y + 1); }
		if(x + 1 < n && y + 1 < n && !metrix[x][y + 1] && !metrix[x + 1][y]) { dfs(null, x + 1,y + 1); }
	}

 

 

마지막으로 종점에 따라 탐색을 진행하고 답을 출력하는 메소드를 선언해주도록 하겠다.

종점이 벽이 아닌경우 탐색을 진행한다.

이때 인자로 주는값은 가로방향, 그리고 시작점인 (0,1)이 된다.

 

	void run() {
		if(!endChk()) { dfs(false,0,1); }
		System.out.print(ans);
	}

 

 

이제 main에서 코드를 작성해 실행한다면

 

	public static void main(String[] args) {
		BOJ17070Sol instance = new BOJ17070Sol();
		instance.run();
	}

 

 

예제에 대해 정확한 답을 내는것을 확인할 수 있다.

 

아래는 코드의 전문이다.

 

package boj5;

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

public class Boj17070 {
	
	public static void main(String[] args) {
		BOJ17070Sol instance = new BOJ17070Sol();
		instance.run();
	}

}

class BOJ17070Sol {
	
	private boolean[][] metrix;
	private int n,ans;
	
	BOJ17070Sol() {
		try {
			init();			
		}catch (IOException e){
			e.printStackTrace();
		}
	}
	
	private void setMetrix() { metrix = new boolean[n][n]; }
	
	private void init() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(in.readLine());
		setMetrix();
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j = 0; j < n; j++) {
				if(st.nextToken().equals("1")) { metrix[i][j] = true; }
			}
		}
		in.close();
	}
	
	private boolean endChk() {
		return metrix[n - 1][n - 1];
	}
	
	private void dfs(Boolean way,int x, int y) {
		if(x == n - 1 && y == n - 1) {
			ans++;
			return;
		}
		if(x == n || y == n || metrix[x][y]) { return; }
		
		if(way == null || way) { dfs(true, x + 1, y); }
		if(way == null || !way){ dfs(false, x, y + 1); }
		if(x + 1 < n && y + 1 < n && !metrix[x][y + 1] && !metrix[x + 1][y]) { dfs(null, x + 1,y + 1); }
	}
	
	void run() {
		if(!endChk()) { dfs(false,0,1); }
		System.out.print(ans);
	}
}