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

문제

BOJ 17070 : 파이프 옮기기 1 - https://www.acmicpc.net/problem/17070

풀이

DP로도 풀이할 수 있는 것 같은데, 그냥 BFS로 풀이했다.

[조건]

1. 현재 방향이 가로일때

   • 가로로 간다
   • 대각선으로 간다

2. 현재 방향이 세로일 때

   • 세로로 간다
   • 대각선으로 간다

3. 현재 방향이 대각선일 때

   • 가로로 간다
   • 세로로 간다
   • 대각선으로 간다
   
   

각각의 조건에 맞추어 벽이 있는지, n의 범위를 벗어나지는 않는지 확인 후에 큐에 넣어주면 된다.

(N,N)까지 도달하는 케이스의 개수를 구해야 하므로 도달했을 때 하나씩 카운트 해주었다.

참고 map[n][n]이 벽일 경우에 대한 시간이 오래 걸리는 케이스가 있나보다. map[n][n]이 1일 경우 어짜피 어떤 경로든 도달할 수 없으므로 예외처리 해주었더니 시간초과에서 벗어났다!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static class Loc{
        int i;
        int j;
        int direction;

        public Loc(int i, int j, int d) {
            this.i = i;
            this.j = j;
            this.direction = d;
        }
    }

    static int[][] map;
    static int n;

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

        map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(inputs[j-1]);
            }
        }

        if(map[n][n]==1){
            System.out.println(0);
            return;
        }

        // BFS
        Queue<Loc> q = new LinkedList<>();
        q.add(new Loc(1, 2, 0));

        int count = 0;

        while (!q.isEmpty()) {
            Loc now = q.poll();

            if (now.i == n && now.j == n) {
                count++;
                continue;
            }

            if (now.direction == 0) { // 현재 방향이 가로 (0) -> 가로(0) or 대각선(2)

                if(isPossible(now, 0)){ // 가로 : 벽이 아니면
                    q.add(new Loc(now.i, now.j + 1, 0));
                }

                if(isPossible(now, 2)) { // 대각선
                    q.add(new Loc(now.i + 1, now.j + 1, 2));
                }

            }else if(now.direction == 1){ // 현재 방향이 세로 (1) -> 세로(1) or 대각선(2)
            
                if(isPossible(now, 1)){ // 세로
                    q.add(new Loc(now.i+1, now.j, 1));
                }

                if(isPossible(now, 2)) { // 대각선
                    q.add(new Loc(now.i + 1, now.j + 1, 2));
                }
                
            }else{ // 현재 방향이 대각선 (2) -> 가로(0) or 세로(1) or 대각선(2)
            
                if(isPossible(now, 0)){ // 가로 : 벽이 아니면
                    q.add(new Loc(now.i, now.j + 1, 0));
                }
                
                if(isPossible(now, 1)){ // 세로
                    q.add(new Loc(now.i+1, now.j, 1));
                }
                
                if(isPossible(now, 2)) { // 대각선
                    q.add(new Loc(now.i + 1, now.j + 1, 2));
                }
                
            }

        }

        if(count==0) {
            System.out.println(0);
        }else {
            System.out.println(count);
        }
    }

    public static boolean isPossible(Loc now, int direction){ // 움직일 위치에 벽이 있는지 확인하는 메소드

        switch (direction){
            case 0 :
                return now.j+1<=n && map[now.i][now.j+1] != 1;
            case 1:
                return now.i+1<=n && map[now.i+1][now.j] != 1;
            case 2:
                return now.i+1<=n && now.j+1<=n && map[now.i][now.j + 1] != 1 && map[now.i + 1][now.j + 1] != 1 && map[now.i + 1][now.j] != 1;
        }

        return false;

    }

}

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 메모

• 그림과 조건에 쫄지 말자! 조건대로 차근차근 구현하면 풀리는 문제였다.

참고 사이트

딱히 없음