탈주범 검거

코테 준비하면서 처음으로 스스로 풀어서 맞춘 문제다! 너무 감동적이다.. 그간 울면서 코딩한 보람이 느껴졌다..거두절미하고

문제 정리

일단 이 문제는 BFS로 푸는 문제 같았다. 그런데 BFS에서, 다음 칸으로 이동할 때, 그 방향과 좌표를 어떻게 결정하느냐가 관건이다. 현재의 터널 모양에 따라 다음 이동할 방향과 좌표가 결정된다.

  1. 터널 모양 별로 이동가능한 방향 벡터(상하좌우 = 0123)을 저장한다.

  2. 1에서 터널 id별로 이동 가능한 방향들이 존재하기 때문에 이 방향 벡터대로 다음 이동 방향과 좌표가 결정되며, 큐에 삽입하면 된다!

시간 L이 주어지는데, 이 L값은 무엇을 의미하는 걸까?생각해봤다. 직관적으로, BFS가 걸리는 시간을 의미하는 것이였다. 하지만 위에 1,2에서 언급한 것처럼, 상/하/좌/우 4가지 방향 모두 이동할 수 있는 것이 아니라 현재의 터널 모양에 따라 이동 방향과 좌표, 시간이 기록 되는 칸이 달라진다.

다음 칸으로 이동하면 시간이 +1씩 증가하지만, 이 Time 값이 L이내인 칸 갯수를 찾아야하기 때문에 이 BFS 문제에서는 각 칸의 시간을 기록하는 2차원 배열을 생성하고, 각 칸에 걸린 시간을 기록하여 0을 제외한 L이하인 칸 갯수를 카운팅해주었다! => 처음 돌려봤을 때 틀린 이유 : 방향 벡터를 델타어레이에서 가져온 게 아니라 그 방향 벡터 자체로 해버려서 틀렸다는 것을 알 수 있었음. int nx = cur.x + dx[3]; 이렇게 되야하는데 델타어레이 없이 int nx = cur.x + 3; 이렇게 방향 벡터 조회만 하고 그 값을 그대로 방향설정하는 데 써버려서 틀림.

  • 디버깅의 중요성1⭐️(걍 에러 원인을 잘 찾아냈다는 말) 오답이 나오길래 Time을 기록해봤는데 BFS를 시작하는 맨홀자리만 1이 기록되고, BFS가 더 진행X. 2차원 배열 형태로 행의 인덱스를 1번부터 시작해서 각 인덱스에 해당하는 터널의 이동가능한 방향 벡터 인덱스를 저장해주었다. ex) 1번 터널 : 상하좌우 로 이동가능하기 때문에 possibleDir[1] 에는 {0,1,2,3}이 저장되어있고, possibleDir[1]의 길이만큼, 방향을 반복해주면 된다. =>현재 터널의 모양 int curTernal = Map[cur.x][cur.y]; => for(int d=0;d< possibleDir[curTernal].length;d++) { int nx = cur.x+dx[ possibleDir[curTernal][d] ]; 방향 벡터 dx에서의 인덱스로 들어가야하는데 방향벡터를 조회한 것에 불과한 possibleDir[curTernal][d]까지만 해버려서 틀렸다. 상하좌우 중에 연결되어있는, 이동가능한 좌표로 이동해야한다. 그렇기 때문에 행이나 열 값이 1차이가 나야하는데 2이상의 행값이 차이가 나서 이상하게 생각해서 디버깅해보니 원인을 알 수 있었다.

  • 디버깅의 중요성2⭐️ 50개의 테스트 케이스 중에서 1개의 테스트 케이스만 제외하고 통과했다. 즉, 49개의 웬만한 테스트 케이스들은 로직이 다 통과했다는 것이다. 처음으로 돌아가 문제를 다시 풀어보기로 했다. Time 배열을 찍어보니, BFS를 시작하는 맨홀위치에 Time 값이 1이 아니라 1보다 큰 값들이 들어있었다. 맨홀의 위치좌표를 재방문했다는 것을 의미했다. 그리고 이것은 처음에 맨홀위치에서 BFS 시작할 때, 큐에 넣어주고 나서 방문체크를 하지 않았다는 것을 의미했기 때문에 에러 원인을 바로 찾을 수 있었다! 운 좋게(?)

3. NxM 크기의 정수형 배열 Time에 각 칸에 이르는 BFS 시간을 기록.

어려웠던 부분/좀 까다로웠던 부분

테스트케이스 2번에서 (0,0)에 터널이 존재하기 때문에 이동가능하다고 생각할 수 있지만, 단순히 터널이 존재한다고 해서 이동할 수 있는 것은 아니다. 문제에서 나와있듯이 현재의 칸과 다음 칸이 "연결" 되어 있어야한다.

따라서 현재의 터널 모양으로 다음 이동 방향과 좌표만 결정하는 게 아니라, 연결 가능한지 여부도 결정해야한다! 다소 복잡해서 논리적인 단계별로 생각하는 것이 정말 중요했다.

현재 위치에서 터널 모양이 위로 향하더라도, 위에 있는 칸이 연결되어있어야한다.

필요한 정보 ① 현재의 터널 모양 : Map[x][y] ② 현재 위치에서 이동할 방향 벡터// 2차원 배열의 행번호에서 있는지 확인하면 됨 ③ 다음 이동할 칸의 터널 모양 => 상,하,좌,우 방향 별로 연결 가능한 터널 모양이 다르다. 따라서 각 4가지 방향에 대해 연결 가능한 터널 모양의 번호를 저장한다 => 4*4 정수형 배열 possibleTernal에 저장

따로 함수로 구현한다. 매개변수로 필요한 정보 ①,②,③을 넣어준다. isConnected(①,②,③) : possibleTernal의 ② (이동할 방향벡터) 행에 ③이 있는지 확인한다. 있으면 연결되어있다는 것을 의미하므로 true를 리턴하고, 그렇지 않으면 false를 리턴함으로써 연결 여부를 확인할 수 있다!(내가 생각했지만 정말 잘 생객해낸듯!뿌듯뿌듯)

연결 여부 확인할 때, 해당 행에 숫자가 존재하는지 찾을 때 시간복잡도를 생각해보면 선형의 시간복잡도를 띈다. 즉, 4개의 요소가 있다면 4개의 요소를 다 확인하기 때문에 O(n)이다. 이번 문제에서는 탐색하는 요소가 4개밖에 없었지만, 저번 카카오 문제 같은 경우, 탐색할 대상이 매우 많다면, 먼저 숫자크기 순으로 정렬한 후 이분 탐색으로 진행하면 시간 복잡도를 줄일 수 있는 것 같았다. 아래 코드는 {80,100,150,150,150,200,260} 리스트에서 150이 처음 나오는 인덱스를 구하는 코드이다. 150이 나오는 인덱스를 찾기 위해 이분적으로 나눠서 진행하는 것을 알 수 있다.

while(start<=end){
            int mid=(start+end)/2;
            if(list.get(mid)<score){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
        
        return list.size()-start;

아래와 같은 컴파일 오류가 뜬다면 클래스 이름을 "Solution"으로 하지 않아서 java 코드 8번째 줄에 에러가 났다는 뜻이다. ArrestPrisoner 클래스는 ArrestPrisoner 이름 파일로 가라~ 여긴 "Solution " 이름의 클래스만 받는다~ 라고 생각하면 된다.

Previous등산로 조성Next수영장

Last updated