BEAKJOON / 백준 - JAVA 17070번 파이프 옮기기 1

2024.09.15기준 - 골드5

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 여러가지 파이프를 이용해 가장 끝 지점까지 도달하도록 하는 방법의 개수를 출력하는 문제입니다.

 

문제 접근

1. 파이프에 경로에 따라 움직일 수 있는 방향이 제한 되기 때문에, 파이프의 방향에 주의합니다.
2. 모든 방향을 다 탐색하기 위해 탐색할 방향을 체크해주고 재귀를 빠져나오면서 체크를 해제를 해주었습니다.

1. 입력받은 집의 구조를 배열에 저장하면서 벽의 위치를 체크해줍니다.

home = new int[n][n];
visit = new boolean[n][n];

StringTokenizer st;
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());

    for (int j = 0; j < n; j++) {
        home[i][j] = Integer.parseInt(st.nextToken());

        // 벽은 갈 수 없게 미리 true로 설정
        if (home[i][j] == 1) {
            visit[i][j] = true;
        }
    }
}

 

2. 처음에는 무조건 가로로되어 있는 (0, 0), (0, 1)의 파이프에서 시작을 해 먼저 체크 후 함수를 호출합니다.

// 출발 위치 체크
visit[0][0] = true;
visit[0][1] = true;

// 함수 호출
recur(0, 1, 1);

 

3. 함수를 생성합니다.

3-1. 우선 집의 범위 안에 해당되는지 체크해주는 함수를 생성했습니다.

// 집의 범위를 넘어가는지 확인하는 함수.
private static boolean check(int y, int x) {
    return 0 <= y && 0 <= x && y < n && x < n;
}

 

3-2. 목표지점에 도달했는지 체크해주는 함수를 생성했습니다.

// 목표지점에 도달했는지 체크해주는 함수.
private static boolean countcheck(int y, int x) {
    return y == n - 1 && x == n - 1;
}

 

3-3. 파이프가 목표지점까지 도달하는데 가는 방법을 찾아주는 함수를 생성합니다.

// 파이프의 경로를 계산하는 함수.
// c : 이동 방향을 숫자로 표시
// 1 → 가로, 2 → 세로, 3 → 대각선
private static void recur(int y, int x, int c) {
int nexty = y + 1;
int nextx = x + 1;

// 대각선
// 대각선은 3칸이 비어있어야 갈 수 있기 때문에 3칸을 비교합니다.
if (check(nexty, nextx) && !visit[y][nextx] && !visit[nexty][x] && !visit[nexty][nextx]) {
    if (countcheck(nexty, nextx)) { // 끝에 도달했다면
        count++;
    } else {
        // 움직이면서 3칸을 전부 체크
        visit[nexty][nextx] = true;
        visit[y][nextx] = true;
        visit[nexty][x] = true;

        // 이동한 위치로 재귀
        recur(nexty, nextx, 3);

        // 돌아오면서 다시 체크를 풀어준다.
        visit[nexty][nextx] = false;
        visit[y][nextx] = false;
        visit[nexty][x] = false;
    }
}

// 세로
// 현재 이동한 방향이 대각선이나 세로라면
if (c == 2 || c == 3) {
    nexty = y + 1;

    if (check(nexty, x) && !visit[nexty][x]) {
        if (countcheck(nexty, x)) { // 끝에 도달했다면
            count++;
        } else {
            // 움직이면서 1칸을 체크
            visit[nexty][x] = true;

            // 움직인 좌표로 재귀 호출
            recur(nexty, x, 2);

            // 다시 돌아오면서 체크 해제
            visit[nexty][x] = false;
        }
    }
}

// 가로
// 현재 이동한 방향이 가로나 대각선이라면
if (c == 1 || c == 3) {
    nextx = x + 1;

    if (check(y, nextx) && !visit[y][nextx]) {
        if (countcheck(y, nextx)) { // 끝에 도달했다면
            count++;
        } else {
            // 움직이면서 1칸을 체크
            visit [y][nextx] = true;

            // 움직인 좌표로 재귀 호출
            recur(y, nextx, 1);

            // 다시 돌아오면서 체크 해제
            visit[y][nextx] = false;
        }
    }
}
}

• 파라미터의 c는 파이프의 방향을 뜻합니다( 1 → 가로, 2 → 세로, 3 → 대각선)
• 어떤 방향으로 되어 있든 대각선은 모두가 이동가능하기 때문에 바로 검사를 시작합니다.
• 대각선으로 이동하는 3개의 공간이 비어있고, 가는 방향이 집의 범위를 벗어나지 않는다면,
  1. 이동시 지점이 목표지점이라면 count를 올려줍니다.
  2. 아니라면 대각선 이동시 필요한 위치를 전부다 true로 표시한 뒤 재귀호출을 해줍니다.
  3. 재귀 호출 후 다시 돌아올 때, 이동한 3개의 위치를 다시 false로 변화시켜 다른 방향으로도 갈 수 있게 해줍니다.
• 만약 현재 파이프가 대각선이나 세로로 되어있다면 세로로 움직일 수 있는 파이프 조건문에 들어가게 됩니다.
  1. 조건문 안에 내용은 대각선을 이동할 때에 내용과 같습니다.
• 만약 현재 파이프가 대각선이나 가로로 되어있다면 가로로 움직일 수 있는 파이프 조건문에 들어가게 됩니다.
  1. 조건문 안에 내용은 대각선을 이동할 때에 내용과 같습니다.

4. 이렇게 나온 count수를 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	static int n, count = 0;
	static int[][] home;
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine()); // 집의 크기
		
		home = new int[n][n];
		visit = new boolean[n][n];
		
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < n; j++) {
				home[i][j] = Integer.parseInt(st.nextToken());
				
				// 벽은 갈 수 없게 미리 true로 설정
				if (home[i][j] == 1) {
					visit[i][j] = true;
				}
			}
		}
		
		// 출발 위치 체크
		visit[0][0] = true;
		visit[0][1] = true;
		
		// 함수 호출
		recur(0, 1, 1);
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 파이프의 경로를 계산하는 함수.
	// c : 이동 방향을 숫자로 표시
	// 1 → 가로, 2 → 세로, 3 → 대각선
	private static void recur(int y, int x, int c) {
		int nexty = y + 1;
		int nextx = x + 1;
		
		// 대각선
		// 대각선은 3칸이 비어있어야 갈 수 있기 때문에 3칸을 비교합니다.
		if (check(nexty, nextx) && !visit[y][nextx] && !visit[nexty][x] && !visit[nexty][nextx]) {
			if (countcheck(nexty, nextx)) { // 끝에 도달했다면
				count++;
			} else {
				// 움직이면서 3칸을 전부 체크
				visit[nexty][nextx] = true;
				visit[y][nextx] = true;
				visit[nexty][x] = true;
				
				// 이동한 위치로 재귀
				recur(nexty, nextx, 3);
				
				// 돌아오면서 다시 체크를 풀어준다.
				visit[nexty][nextx] = false;
				visit[y][nextx] = false;
				visit[nexty][x] = false;
			}
		}
		
		// 세로
		// 현재 이동한 방향이 대각선이나 세로라면
		if (c == 2 || c == 3) {
			nexty = y + 1;
			
			if (check(nexty, x) && !visit[nexty][x]) {
				if (countcheck(nexty, x)) { // 끝에 도달했다면
					count++;
				} else {
					// 움직이면서 1칸을 체크
					visit[nexty][x] = true;
					
					// 움직인 좌표로 재귀 호출
					recur(nexty, x, 2);
					
					// 다시 돌아오면서 체크 해제
					visit[nexty][x] = false;
				}
			}
		}
		
		// 가로
		// 현재 이동한 방향이 가로나 대각선이라면
		if (c == 1 || c == 3) {
			nextx = x + 1;
			
			if (check(y, nextx) && !visit[y][nextx]) {
				if (countcheck(y, nextx)) { // 끝에 도달했다면
					count++;
				} else {
					// 움직이면서 1칸을 체크
					visit [y][nextx] = true;
					
					// 움직인 좌표로 재귀 호출
					recur(y, nextx, 1);
					
					// 다시 돌아오면서 체크 해제
					visit[y][nextx] = false;
				}
			}
		}
	}
	
	// 목표지점에 도달했는지 체크해주는 함수.
	private static boolean countcheck(int y, int x) {
		return y == n - 1 && x == n - 1;
	}
	
	// 집의 범위를 넘어가는지 확인하는 함수.
	private static boolean check(int y, int x) {
		return 0 <= y && 0 <= x && y < n && x < n;
	}
}