백준 17070번: 파이프 옮기기 1

문제 설명

• 시작점에 놓인 파이프를 (N,N)으로 옮기는 문제입니다.

접근법

• (0,1)부터 한칸씩 전진하는 것과 동일합니다.
• 길을 찾는 문제이기 때문에 완전탐색을 사용할 수 있습니다.
• 파이프를 놓는게 아니라 미는거기 때문에 board를 변경할 필요는 없습니다.
• 해당 길에 파이프를 옮겨보고 안되면 가지치기 하는 백트래킹 방법을 사용할 수 있습니다.

pseudocode

main(){
(0,1)에서 백트래킹 시작
}
백트래킹(){
(x,y)가 board를 벗어나거나 (x,y)가 벽이면 제외
대각선 파이프일 때 (x-1,y)혹은 (x,y-1)이 벽이면 제외
(N,N)이 벽이 아니며, (x,y)가 (N,N)에 도달했으면 가능한 경로로 인식
switch(내 파이프){
	case 내가 가로파이프면:
		가로파이프 연결하고 다음으로 넘어가기
        or // or로 표현했지만 백트래킹으로 두 경우를 모두 진행해봐야야 합니다.
    	대각선파이프 연결하고 다음으로 넘어가기
	case 내가 대각선파이프면:
		가로파이프 연결하고 다음으로 넘어가기
        or
    	대각선파이프 연결하고 다음으로 넘어가기
        or
    	세로파이프 연결하고 다음으로 넘어가기
	case 내가 세로파이프면:
		세로파이프 연결하고 다음으로 넘어가기
        or
    	대각선파이프 연결하고 다음으로 넘어가기
}
}

정답

import java.util.*;

public class Main {
	static int[] dx = { 0, 1, 1 };
	static int[] dy = { 1, 1, 0 };
	static int cnt = 0;
	static int N;
	static int[][] board;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		BackT(0, 1, 0);
		System.out.println(cnt);
	}

	public static void BackT(int x, int y, int pipenum) {
		
		if (x >= N || y >= N || board[x][y] == 1)return; // (x,y)가 board를 벗어나거나 벽에 부딪히면 정답이 될 수 없습니다.
		if (pipenum == 1 && (board[x - 1][y] == 1 || board[x][y - 1] == 1))return; // 대각선으로 놓는 경우에는 추가로 두 곳을 더 확인해야 합니다.
		if (x == N - 1 && y == N - 1 && board[x][y] == 0) { // (x,y)가 마지막 위치에 도착했고, 마지막 위치에 벽이 없다면
			cnt++; // 가능한 경우의 수입니다.
			return;
		}
		switch (pipenum) {
		case 0: // 가로파이프 다음에는 가로 or 대각선 파이프를 놓을 수 있습니다.
			BackT(x + dx[0], y + dy[0], 0);
			BackT(x + dx[1], y + dy[1], 1);
			break;
		case 1: // 대각선 파이프 다음에는 가로 or 세로 or 대각선 파이프를 놓을 수 있습니다.
			BackT(x + dx[0], y + dy[0], 0);
			BackT(x + dx[1], y + dy[1], 1);
			BackT(x + dx[2], y + dy[2], 2);
			break;
		case 2: // 세로파이프 다음에는 세로 or 대각선 파이프를 놓을 수 있습니다.
			BackT(x + dx[2], y + dy[2], 2);
			BackT(x + dx[1], y + dy[1], 1);
			break;
		}

	}

}

기타

틀렸던 부분

• 일단 다음파이프를 다음 BackT에서 유효성을 확인하는 방식이기 때문에 유효성검사가 return보다 먼저 와야 합니다.

// 올바른 정답
if (x >= N || y >= N || board[x][y] == 1)return;
if (pipenum == 1 && (board[x - 1][y] == 1 || board[x][y - 1] == 1))return;
if (x == N - 1 && y == N - 1 && board[x][y] == 0) {
	cnt++;
	return;
}

// 틀렸던 풀이
if (x == N - 1 && y == N - 1 && board[x][y] == 0) {
	cnt++;
	return;
}
if (x >= N || y >= N || board[x][y] == 1)return;
if (pipenum == 1 && (board[x - 1][y] == 1 || board[x][y - 1] == 1))return;

유사한 문제

• 빵집