[백준 / BOJ] 16137 견우와 직녀

문제

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

16137번: 견우와 직녀

견우와 직녀는 여러 섬과 절벽으로 이루어진 크기 N*N 지역에 살고있다.

견우는 0,0에, 직녀는 N,N에 살고있다.

 

까치들은 견우와 직녀를 만나게해주기위해서, 오작교를 만드는데, 오작교는 T주기마다 생성되며, 1분동안 유지된다.

견우는 오작교를 2번이상 연속적으로 건널수없으며, 추가적으로 임의의 절벽에 다리를 하나 생성해서 건널수있다.

 

단, 다리를 생성할때, 교차로에는 짓지못하며, 이미 오작교가 있는곳에도 짓지못한다.

 

이때, 견우가 직녀를 만나는 최소시간을 구하는 문제다.

 

---

풀이

다익스트라 + 구현 문제였다.

문제를 풀 당시, "2번연속으로 건너지못한다"라는 조건을 왔던길을 되돌아가지못한다고 해석해버려서 몇번 틀렸었다.

 

알고리즘의 전체적인 흐름은 문제가 시키는대로 설계하면된다. 단, 이때 주의할 점이 있는데,

 

1. 중복체크를 해주기위해 check배열을 생성할때, 3차원으로 생성해야한다.
-> check[y][x][다리를건설했는가?] = 최솟값

어떠한 위치 y,x에 도착했을때, 임의의 다리를 건설해서 도착한경우와 오작교를 지나 도착한 경우 두가지가 있을수있고, 이것이 점진적으로 어떤 결과를 초래할지 알수없기때문에, 이 처럼 3차원으로 생성해야한다.

 

2. 절벽이 교차하는 지점을 판별해줘야한다.

(이때, BFS를 돌려서 미리 찾아놓는방법도 있겠지만, 조건문만 사용해서 찾을수도있다.)

 

자신의 y-1혹은 y+1이 절벽이라면, 이는 수직절벽이다. 따라서, x+1 과 x-1에는 절벽이 존재하면 안된다.

(당연히 반대의 경우도 마찬가지다)

 

구현은 소스코드를 보도록하자

 

소스코드

    private boolean checkCross(int[][] arr, int y, int x){
        if((!outOfBound(y-1, x) && arr[y-1][x] != 1) || (!outOfBound(y+1, x) && arr[y+1][x] != 1)){
            if((!outOfBound(y, x-1) && arr[y][x-1] != 1) || (!outOfBound(y, x+1) && arr[y][x+1] != 1)) return true;
        }
        if((!outOfBound(y, x-1) && arr[y][x-1] != 1) || (!outOfBound(y, x+1) && arr[y][x+1] != 1)){
            if((!outOfBound(y-1, x) && arr[y-1][x] != 1) || (!outOfBound(y+1, x) && arr[y+1][x] != 1)) return true;
        }
        return false;
    }
    
    private boolean outOfBound(int y, int x){
        return y >= N || x >= N || y < 0 || x < 0;
    }

 

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/16137%20%EA%B2%AC%EC%9A%B0%EC%99%80%20%EC%A7%81%EB%85%80/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃