[17070] 파이프 옮기기1 - Java[자바]

 

 

| 문제 링크

 

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

17070번: 파이프 옮기기 1

 

 

 

 

---

 

 

 

 

| 문제

 

1. 첫째 줄에 입력 값 N(3 ≤ N ≤ 16)이 주어집니다.
2. 그 다음줄 부터 0과 1로 이루어진 NxN 크기의 배열이 주어집니다.
3. 파이프는 가로, 세로, 대각선 세 가지 종류이며, 이어질 수 있는 파이프의 종류와 조건은 다음과 같습니다.
   가로 - 가로, 대각선  |  조건: 배열의 오른쪽 칸이 0이어야함
   세로 - 세로, 대각선  |  조건: 배열의 아래 칸이 0이어야함
   대각선 - 가로, 세로, 대각선  |  조건: 오른쪽, 아래, 오른쪽 아래 대각선 세 칸이 모두 0이어야함
4. 파이프의 첫 시작은 가로 파이프로 (1,2)부터 시작할 수 있습니다.
5. (N,N)에 파이프 끝을 놓을 수 있는 경우의 수를 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 처음에는 BFS로 접근할라 했으나, 최단 경로를 구하는 것이 아닌 모든 경우의 수를 구하는 방식으로 방문처리를 하지 않는 BFS 방식은 DFS보다 많인 비용을 소비하기에 DFS로 접근했습니다.
2. DFS는 (row, col, pipe 종류) 3 가지 파라미터를 받아 진행하였으며, 이전 파이프 종류를 3가지로 나누어 연결할 파이프의 종류별로 범위를 탐색해 파이프를 설치 가능한 경우 나아가는 방식으로 진행했습니다.

 

코드와 주석으로 보시는게 직관적으로 이해가 빠를 것으로 생각됩니다.

 

 

 

 

 

---

 

 

 

 

| 코드

 

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

public class Main {
	
	public static int n;
	public static int cnt;
	public static int[][] maze;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		maze = new int[n][n];
		
		for(int r = 0; r<n; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0; c<n; c++) {
				maze[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0,1,0);
		
		bw.write(String.valueOf(cnt));
		br.close();
		bw.close();
		
	}
	//pipe
	//0: 가로
	//1: 세로
	//2: 대각선
	public static void dfs(int r, int c, int pipe) {
		//파이프가 목적 좌표에 도착한 경우 cnt++
		if(r==n-1 && c==n-1) {
			cnt++;
			return;
		}
		//이전 파이프가 가로인 경우
		if(pipe == 0) {
			//가로로 갈 수 있는지
			if(c+1<n && maze[r][c+1]==0)
				dfs(r,c+1,0);
			//대각으로 갈 수 있는지
			if(r+1<n && c+1<n && maze[r+1][c+1]==0 && maze[r][c+1]==0 && maze[r+1][c]==0)
				dfs(r+1,c+1,2);
		}
		//이전 파이프가 세로인 경우
		if(pipe == 1) {
			//세로로 갈 수 있는지
			if(r+1<n && maze[r+1][c]==0)
				dfs(r+1,c,1);
			//대각으로 갈 수 있는지
			if(r+1<n && c+1<n && maze[r+1][c+1]==0 && maze[r][c+1]==0 && maze[r+1][c]==0)
				dfs(r+1,c+1,2);
		}
		//이전 파이프가 대각선인 경우
		if(pipe == 2) {
			//가로로 갈 수 있는지
			if(c+1<n && maze[r][c+1]==0)
				dfs(r,c+1,0);
			//세로로 갈 수 있는지
			if(r+1<n && maze[r+1][c]==0)
				dfs(r+1,c,1);
			//대각으로 갈 수 있는지
			if(r+1<n && c+1<n && maze[r+1][c+1]==0 && maze[r][c+1]==0 && maze[r+1][c]==0)
				dfs(r+1,c+1,2);
		}
	}

}