백준_17070_파이프옮기기1

 

 

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

17070번: 파이프 옮기기 1

문제를 읽어보면 파이프를 옮겨 왼쪽 아래 끝부분에 도착하는 경수의 수를 모두 구하는 문제이다.

파이프가 가질수 있는 모양은 가로방향 , 세로 방향, 대각선 방향이다. 

이때 가로와 세로 방향일때는 각각 두 가지 방법으로 이동할 수 있고

대각선 방향일 때는 총 세 가지 방향으로 이동할 수 있다.

주의해야 할 점은 대각선 방향으로 파이프를 이동시킬 때 주변 세 칸이 모두 빈칸이 여야 한다

또한 파이프의 오른쪽 끝점만 생각하고 파이프의 왼쪽 꼬리 부분은 신경 쓰지 않아도 된다.

재귀로 완전 탐색을 한다면 간단히 풀 수 있는 문제이다. 

다음은 전체 코드이다.

import java.util.Scanner;
						
public class Bj_17070 {
	static int map[][];
	static int n;		
	static int ans = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
        // 가로방향 1, 세로방향 2, 대각선방향 3 으로 표현해주었다.
        // 파이프의 오른쪽끝점은 좌표(1, 2) 에서 시작한다.
		move(1, 2, 1);
		System.out.println(ans);
		
	}	
	static void move(int x, int y, int dir) {
    // 파이프가 오른쪽 아래 끝점에 도착했다면 ans 를 1 증가시켜준후 종료한다.
		if(x == n && y == n) {
			ans++;
			return;
		}
        // 새롭게 이동할 지점에대한 변수 선언
		int new_x = x + 1;
		int new_y = y + 1;
		switch (dir) {
        //각케이스는 파이프의 방향을 의미한다.
		case 1:
        // 가로 방향일때 오른쪽으로 이동할경우 일단 벽을 나가면 안된다.
			if(new_y <= n) {
            // 새롭게 이동할 지점에 벽(1) 이있으면 안된다.
				if(map[x][new_y] != 1) {
                // 가로방향에서 가로 방향으로 이동하는것이기떄문에 방향 그대로 (dir)
					move(x, new_y, dir);
				}
			}
            // 가로 방향에서 대각선으로 이동할때 역시 벽을 나가면안된다.
			if(new_x <= n && new_y <= n) {
            	// 대각선으로 이동할시에는 총3부분이 빈칸이여야한다.
				if(map[new_x][new_y] != 1 && map[x][new_y] != 1 && map[new_x][y] != 1) {
                // 가로 방향(1) 에서 대각선 방향으로 이동이기 떄문에(1 + 2) dir + 2 를해준다.
					move(new_x, new_y, dir + 2);
				}
			}
			break;
            // 위 1번 케이스에서 설명한것과 같은 방식으로 코드를 구현하면 된다.
		case 2:
			if(new_x <= n) {
				if(map[new_x][y] != 1) {
					move(new_x, y, dir);
				}
			}
			if(new_x <= n && new_y <= n) {
				if(map[new_x][new_y] != 1 && map[x][new_y] != 1 && map[new_x][y] != 1) {
					move(new_x, new_y, dir + 1);
				}
			}
			break;
		case 3:
			if(new_x <= n) {
				if(map[new_x][y] != 1) {
					move(new_x, y, dir - 1);
				}
			}
			if(new_y <= n) {
				if(map[x][new_y] != 1) {
					move(x, new_y, dir - 2);
				}
			}
			if(new_x <= n && new_y <= n) {
				if(map[new_x][new_y] != 1 && map[x][new_y] != 1 && map[new_x][y] != 1) {
					move(new_x, new_y, dir);
				}
			}
			break;
		}
		
	}
	
}