[백준] 17070번 : 파이프 옮기기 1 - 자바(JAVA)

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

17070번: 파이프 옮기기 1

 

문제 해석

N x N 크기의 집이 존재합니다.

각 칸은 (r , c)로 나타낼 수 있습니다.

r은 행번호, c는 열 번호입니다.

 

집은 빈칸0 , 벽 1로 이루어집니다.

 

파이프는 항상 빈칸만 차지해야 하며 파이프를 밀 수 있는 방향은  →, ↘, ↓입니다.

밀면서 회전시킬 수 있지만 45도만 회전시킬 수 있습니다.

 

다음 그램은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이며 꼭, 빈칸이어야 하는 곳은 색으로 표시되어 있습니다.

 

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

가장 처음 파이프는 (1,1)과 (1,2)를 차지하고 있고, 방향은 가로일때 파이프의 끝을 (N, N)으로 이동시키는 방법의 개수를 구해보자.

 

 

문제 풀이 전 설계

벽이 있으면 파이프는 이동하지 못하며 대각선아래로 이동하는 경우에는 빈칸 체크 가는 방향 기준으로 왼쪽, 위도 검사해주어야 합니다.

 

BFS를 돌리며 Queue에 경로를 쌓아나가는데 만약 파이프가 벽에 막히는경우에는 Queue에서 빼기만 하면서 최종적으로 N, N에 도착하는 수를 count 해줍니다.

 

2가지의 경우의 수는 같은 좌표로 이동하지만 서로 다른 경우의 수이기 때문에 visited 배열은 사용하지 않음 
→ → → → ↘
↘ → → → →

 

문제 풀이하면서

BFS로 풀었는데 시간 초과가 났습니다.

이때 Queue를 ArrayList로 바꿔서 로직은 똑같이 풀면 해결은 되었습니다.

또한 House [N-1][N-1] == true 일 때는 어차피 답을 찾지 못하니까 0을 출력하고 끝내라는 구문을 넣으니 Queue를 사용해도 통과되었습니다.

 

Queue vs ArrayList의 시간 차이에 대해서는 한번 조사해볼 예정입니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_17070_파이프옮기기1 {

	static class Pos {
		int y;
		int x;
		int direct;

		public Pos(int y, int x, int direct) {
			super();
			this.y = y;
			this.x = x;
			this.direct = direct;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", direct=" + direct + "]";
		}

		

	}
	
	static final int RIGHT = 0;
	static final int DIAGONAL = 1;
	static final int DOWN = 2;
	
	static boolean[][] house;
	static int N;
	static int result;
	static int[] dy = { 0, 1, 1 };
	static int[] dx = { 1, 1, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		house = new boolean[N][N];

		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				if (Integer.parseInt(st.nextToken()) == 0) {
					continue;
				}
				house[i][j] = true;
			}
		}

		if(house[N-1][N-1]) {
			System.out.println(result);
			return;
		}
		
		BFS();
		
		System.out.println(result);
	}

	private static void BFS() {
		//List<Pos> bfsQ = new ArrayList<Pos>();
		Queue<Pos> bfsQ = new LinkedList<Pos>(); 
		// 2가지의 경우의수는 같은 좌표로 이동하지만 서로 다른 경우의수이기 때문에 visited 배열은 사용하지 않음
		// → → → → ↘
		// ↘ → → → →
		// 방향 표시 → : 0, 방향표시 ↘ : 1, 방향표시 ↓ : 2
		bfsQ.add(new Pos(0, 1, RIGHT));
		
		
		while (!bfsQ.isEmpty()) {
			//Pos current = bfsQ.remove(bfsQ.size()-1);
			Pos current = bfsQ.poll();
			int currentY = current.y;
			int currentX = current.x;
			int currentDirect = current.direct;

			if (isDestination(currentY, currentX)) {
				result++;
				continue;
			}

			for (int k = 0; k < 3; k++) {

				// 현재 방향이 → 라면 아래로는 갈 수 없음
				if (currentDirect == RIGHT) {
					if (k == DOWN) {
						continue;
					}
				}
				// 현재 방향이 ↓라면 오른쪽으로 갈 순 없음
				if (currentDirect == DOWN) {
					if (k == RIGHT) {
						continue;
					}
				}

				int tempY = currentY + dy[k];
				int tempX = currentX + dx[k];

				// 좌표의 유효성 검사
				// 주변의 빈칸체크!
				// 대각선으로 가는 경우라면 해당칸 위와 왼쪽도 확인해야한다.
				if (!isValid(tempY, tempX, k)) {
					continue;
				}				
				bfsQ.add(new Pos(tempY, tempX, k));
			}

		}

	}

	private static boolean isValid(int currentY, int currentX, int k) {
		// house[currentY][currentX] = true이면 벽임
		if (k != DIAGONAL) {
			return currentY >= 0 && currentY <= N - 1 && currentX >= 0 && currentX <= N - 1
					&& !house[currentY][currentX];
		}

		// 대각선으로 이동하는 경우라면!
		// 대각선 검사
		
		boolean condition1 = currentY >= 0 && currentY <= N - 1 && currentX >= 0 && currentX <= N - 1
				&& !house[currentY][currentX];
		// 대각선 이동기준 왼쪽검사		
		if(!condition1) {
			return condition1;
		}		
		//3가지조건을 모두 충족해야함.
		return !house[currentY][currentX-1] && !house[currentY-1][currentX];
		

	}

	static boolean isDestination(int currentY, int currentX) {
		return currentY == N - 1 && currentX == N - 1;
	}

}