BOJ - 견우와 직녀 16137번 (JAVA)

❓ 문제 - 백준 견우와 직녀 16137번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/16137)

16137번: 견우와 직녀

 

 

 

📝 문제해결법

1. 문제 해석

• 견우와 직녀는 오작교를 통해 건너 만날 수 있으며, 오작교는 몇 분을 주기로 짓고 해체하는 작업을 수행한다. 그리고 오작교는 1분 동안 유지할 수 있으며, 두 번 연속으로 오작교는 걷지 못 한다.
• 절벽을 정확히 하나 골라서 주기가 M분인 오작교를 하나 더 놓을 수 있으며 절벽이 가로와 세로로 교차하는 곳에 오작교를 놓을 수 없다.
• 견우(0,0)가 일반적인 땅 or 오작교로 직녀(n-1, n-1)에게 도착할 수 있는 최소의 시간을 구해야한다.

 

2. 해결 방법

• BFS를 통해 견우에서 직녀로 갈 수 있는 최소 시간을 구하면 된다.
• 우선 절벽에 무조건 하나의 오작교를 설치해야 하므로 check()함수를 통해 절벽이 가로로 세로로 교차하는지 확인하고 오작교를 놓을 수 있는 곳이라면 그곳에 오작교를 설치한 뒤에 bfs 함수를 통해 최소 시간을 계속 갱신한다.
• BFS 함수 내에서는 이동할 곳이 일반 땅이라면 이동하고, 만약 현재 있는 곳이 땅일 때 주기에 맞는 오작교라면 이동처리하고 주기에 맞지 않는 곳이라면 주기에 맞을 때까지 queue에 node.dis만 1증가시키고 기다리도록 구현한다.

 

3. 삽질 & 느낀점

• 문제 한 줄마다 엄청난 힌트와 히든 케이스가 숨겨진 문제였다..
• 일단 처음에 bfs로 구현을 시작하였는데 오작교를 설치했는지 안했는지 여부에 따라 이동하면서 최소시간을 구했는데 자꾸 틀렸다고 떠서.. 다시 다른 분들의 풀이를 참고하니 
• 오작교 하나는 무조건 설치해야함 -> 따라서 한 곳을 설치한 상태에서 bfs 돌리기 해야함..!
• 그리고 bfs 내에서도 현재 땅일 때만!!!!!!!!! -> 옆에 주기가 맞는 오작교로 이동 가능
• 그리고 현재 땅이고, 옆에 주지가 맞지 않은 오작교가 있으면 못 가는 것이 아닌 주기가 맞을 때까지 현재 위치에서 기다렸다가 이동하면 된다..
• 이런 문제에 하나씩 디테일을 담은 것은 처음 봤다.. 앞으로 bfs + 구현 문제는 이런 디테일 하나씩을 분석하면서 히든 케이스에 대비할 수 있도록 해야겠다.

 

 

💻 소스코드 

// BOJ - 견우와 직녀 (16137번)
// BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_12783 {
    public static int n, m;
    public static int[][] map;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static int min_time = Integer.MAX_VALUE;
    public static class Node {
        int x;
        int y;
        int dis;

        public Node(int x, int y, int dis){
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[i][j] == 0){
                    if(!check(i, j)){
                        map[i][j] = m;
                        boolean[][] visited = new boolean[n][n];
                        bfs(visited);
                        map[i][j] = 0;
                    }
                }
            }
        }


        System.out.println(min_time);
    }

    public static void bfs(boolean[][] visited){

        Queue<Node> q = new LinkedList<>();
        visited[0][0] = true;
        q.add(new Node(0, 0, 0));
        while (!q.isEmpty()){
            Node node = q.poll();
            if(node.x == n-1 && node.y == n-1){
                min_time = Math.min(min_time, node.dis);
                return;
            }
            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(visited[nx][ny]) continue;

                if(map[nx][ny] == 1){
                    visited[nx][ny] = true;
                    q.add(new Node(nx, ny, node.dis+1));
                } else if(map[nx][ny] >= 2 && map[node.x][node.y] == 1){
                    if((node.dis+1) % map[nx][ny] == 0){
                        visited[nx][ny] = true;
                        q.add(new Node(nx, ny, node.dis+1));
                    } else {
                        q.add(new Node(node.x, node.y, node.dis+1));
                    }
                }
            }
        }

        return;
    }

    public static boolean check(int x, int y){

        for(int d=0;d<4;d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            int cnt = 0;
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(map[nx][ny] == 0) cnt++;
            nx = x + dx[(d+1)%4];
            ny = y + dy[(d+1)%4];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(map[nx][ny] == 0) cnt++;
            if(cnt == 2) return true;
        }
        return false;
    }

}