[SW Experts Academy] 1226. 미로1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

SW Expert Academy

<서론>

문제 링크는 위에.. 오랫동안 알고리즘 쉬다가 다시 공부를 시작하려한다. 이번 문제는 복귀 문제. 한창 풀때였으면 기계적으로 빠르게 풀었겠지만, 너무 오랜만에 해서 그런지 좀많이 허둥댔다. 역시 알고리즘은 빡세게 안할 때라도 하루에 한문제는 풀어야할 것 같다.

이번 문제는 제목에서 알 수 있듯이 경로 탐색 문제! 그럼 이번 문제도 풀어보자.

---

 

 

<본론>

이번엔 테스트 케이스 수를 입력 받아서 그 수만큼 반복문을 실행하는 것은 아니고, 테스트 케이스는 10개로 고정되어있다. 처음 받는 숫자는 테스트케이스 개수가 아니라 테스트케이스 번호라는 것을 알아야한다. 이걸 처리하는 방법은 많겠지만, 난 귀찮아서 입력만 받고 그냥 넘겼다. 이번 문제는 경로 문제답게 간단하게 bfs 방법을 이용해서 풀었다. 알고리즘은 별반 다를 것 없다.

1. 시작 좌표를 큐에 저장
2. 큐가 빌 때까지 또는 목표에 도착할 때까지, 다음을 반복
  2-1 큐 pop
  2-2 큐에서 꺼낸 좌표의 4방향 체크
    2-2-1 4방향에 있는 값을 방문한 적이 없고, 0이면 큐에 추가
    2-2-2 4방향에 있는 값을 방문한 적이 없고, 3이면 목표 도착 체크

평범한 bfs 문제였다. 특별히 신경써서 처리할 것도 없고, 최단 경로의 길이를 구하는 문제도 아니고 그저 도착할 수 있는지만 확인하는 문제. 그런데 오랜만에 풀어서 어처구니 없는 실수들을 반복했다. 다음은 실수들에 대한 정리이다. 바로 코드를 보고 싶은 사람은 바로 결론으로..

 

1. Input 값 처리 실수

이 문제를 풀 때 발생한 첫 예외처리. 로직을 확인하기도 전에 값을 입력받을 때 문제가 있었다. 아무 생각 없이 nextInt() 메소드를 이용해서 MAP[][] 배열에 값을 넣으려고 했는데, 모든 숫자가 붙어있어서 nextInt를 해버리면 1자리 숫자가 아닌 16자리 숫자로 입력되는 것이었다. 하는 수 없이 String 객체로 입력 받고, split 메소드를 이용해서 잘라 넣었다. MAP 배열을 String 배열로 선언해서 풀 수 있었지만, 이미 모든 로직을 정수형일 경우로 정해놓고 풀어서 input 값을 integer로 파싱했다.

2. 배열 범위 초과

입력 문제를 해결하자 곧바로 다른 예외 발생. 배열 범위를 벗어난다는 어처구니없는 오류였다. 배열을 0,0에서부터 15,15까지 4방향을 체크하게 짜두었는데 가장자리 부분에서 예외가 발생한 것이다. 정말 초보적인 실수를 하고야 말았다. 배열을 2칸 키워서 처리했다. 이래서 알고리즘은 쉬면 안되는 것이다.

3. 무한 루프

배열까지 처리했더니 프로그램이 종료가 안되는 것이었다. 그래서 디버깅 모드로 확인했더니... 블로그에 적지말까? 하고 고민했을 정도로 창피한 실수를 했다. que의 첫번째 원소를 가져오기만 하고 제거를 안한 것이었다. 큐가 빌 때까지 도는 반복문이었기 때문에 곧바로 무한루프.. 버그를 고치면서도 스스로 민망했다.

4. 시작점 설정 실수

아직도 실수가 남았다. 배열을 2칸 늘렸으니 저장되는 시작점의 위치도 그에 따라 바꿔야하는데 그러질 못했다. 그래서 자꾸 답이 다른 답이 나오는 것이었다. 디버깅할 때도 도대체 왜 시작점을 이상하게 잡는 건지 한참을 고민했다. 시작점을 찾는 if문에는 이쁘게 잘 j+1이라고 적어놓고선 실제로 저장할 땐 그냥 j만 저장했다. 간신히 찾고 다시 돌린 결과 정답.. 힘들었다.

 

<결론>

요약은 패스.

package d190610;
 
import java.util.LinkedList;
import java.util.Scanner;
 
// 1226 미로 1
public class Solution {
 
    static int[][] MAP = new int[18][18];
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
 
    static public void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        for(int testCase = 1; testCase <= 10; testCase++) {
            boolean[][] visited = new boolean[18][18];
            String t = sc.next();
            int[] start = new int[2];
            int ans = 0;
            for(int i=0; i<18; i++) {
                if(i!=0 && i!=17){
                    String str = sc.next();
                    String[] strArr = str.split("");
                    for(int j=0; j<strArr.length; j++) {
                        MAP[i][j+1] = Integer.parseInt(strArr[j]);
                        if(MAP[i][j+1]==2) {
                            start[0] = j+1;
                            start[1] = i;
                        }
                    }
                }
                MAP[0][i] = 8;
                MAP[i][0] = 8;
                MAP[i][17] = 8;
                MAP[17][i] = 8;
            }
 
            /*  이건 그냥 MAP 확인용
            System.out.println("====="+testCase);
            for(int i=0; i<18; i++) {
                for(int j=0; j<18; j++) {
                    System.out.print(MAP[i][j]+"");
                }
                System.out.println();
            }
            System.out.println("====="+testCase);
            */
 
            LinkedList<Cord_1226> que = new LinkedList<>();
            que.add(new Cord_1226(start[0], start[1]));
            while(!que.isEmpty()) {
                if(ans==1) break;
                Cord_1226 cd = que.get(0);
                que.removeFirst();
                int x = cd.getX();
                int y = cd.getY();
                for(int dir=0; dir<4; dir++){
                    if(MAP[y+dy[dir]][x+dx[dir]]==0 && !visited[y+dy[dir]][x+dx[dir]]) {
                        que.add(new Cord_1226(x+dx[dir], y+dy[dir]));
                        visited[y+dy[dir]][x+dx[dir]] = true;
                    } else if(MAP[y+dy[dir]][x+dx[dir]]==3 && !visited[y+dy[dir]][x+dx[dir]]) ans = 1;
                }
            }
 
            System.out.println("#"+testCase+" "+ans);
        }
        sc.close();
    }
 
}
 
class Cord_1226{
    private int x;
    private int y;
 
    Cord_1226(){}
 
    Cord_1226(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    public int getX() {
        return x;
    }
 
    public int getY() {
        return y;
    }
 
    public void setY(int y) {
        this.y = y;
    }
 
    public void setX(int x) {
        this.x = x;
    }
 
}
 

;