백준 2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

Source Code : https://github.com/JangAJang/Algorithm/blob/main/백준_그래프와%20순회/벽%20부수고%20이동하기/src/Main.java

처음에 간단한 BFS문제로 알고, 코드를 바로 구상할 수 있었다. 

근데 틀렸다고 나왔다. 

틀린 코드 : https://github.com/JangAJang/Algorithm/blob/main/백준_그래프와%20순회/벽%20부수고%20이동하기(반례에서%20막힘)/src/Main.java 

GitHub - JangAJang/Algorithm: 자바를 사용한 백준 알고리즘 문제답안입니다.

벽을 하나만 부술 수 있고, 그렇게 해서 최종점에 도착했을때의 값을 출력시킨다. 

 

분명 BFS로 계산시에 아무 이상 없다고 생각했다. 

그런데, 명제를 조금 바꿔야했다. 벽을 하나 부술 수 있다. 

 

곰곰히 생각해보면, 벽을 부수고 들어갈 수 있고, 부수지 않고 끝까지 갈 수 있다. 

분명 벽을 하나만 부순다고 했을 때, 벽을 부수지 않고 가는게 더 빠른 경우가 있을 수 있다. 

이런 점을 감안해 코드를 다시 구상했다. 

 

public static class Location{
    int x;
    int y;

    boolean wall_broken;
    int count;

    public Location(int x, int y, int count, boolean wall_broken){
        this.x = x;
        this.y = y;
        this.count = count;
        this.wall_broken = wall_broken;
    }
}

이동 좌표에 대한 값을 다음과 같이 저장했다. count를 이용해 지금 몇번째 이동인지를 표시했다. 또한, 하나의 동선의 개념으로 보았을 때, 벽을 부순 후에 이동하는건지 아닌지도 등록해두었다. 

 

public static void bfs(){
    Queue<Location> queue = new LinkedList<>();
    queue.add(new Location(1, 1, 1, false));
    visited[1][1][0] = true;
    while(!queue.isEmpty()){
        Location now = queue.poll();
        if(now.x == N && now.y == M) {
            System.out.println(now.count);
            return;
        }
        for(int i=0; i<4; i++){
            int newX = x_case[i] + now.x;
            int newY = y_case[i] + now.y;
            if(newX == 0 || newY == 0 || newX > N || newY > M)continue;
            int newCount = now.count+1;
            if(arr[newX][newY] == 0){
                if(!now.wall_broken && !visited[newX][newY][0]){
                    queue.add(new Location(newX, newY, newCount, false));
                    visited[newX][newY][0] = true;
                }
                else if(now.wall_broken && !visited[newX][newY][1]){
                    queue.add(new Location(newX, newY, newCount, true));
                    visited[newX][newY][1] = true;
                }
            }
            else if(arr[newX][newY] == 1 && !visited[newX][newY][1]){
                if(!now.wall_broken){
                    queue.add(new Location(newX, newY, newCount, true));
                    visited[newX][newY][1] = true;
                }
            }
        }
    }
    System.out.println("-1");
}

벽을 부수는 부분을 상당히 하드코딩해두었는데, 이를 설명하자면 다음과 같다. 

1. 첫 좌표를 큐에 넣고, visited를 참으로 해놓는다. 
2. 반복문으로 들어가 다음으로 이동할 수 있는 좌표들을 구한다. 
3. 계산한 좌표는 다음 3가지 경우에만 큐에 넣는다.
   1. 좌표에 벽이 없고, 간 적이 없는 곳일 때
      1. 여태 벽을 부순적이 없을 때
      2. 벽을 한번 부순 후일 때 
   2. 좌표에 벽이 있지만, 부술 수 있을 때
4. 이렇게 최종점까지 가서, 최종점에 도달했을 경우, 이를 출력한다. (마지막에 -1을 출력한다. 이는 도착을 못했을 때 출력되도록 두었다.)

이러한 방식으로 코딩을 진행했다. 

 

문제는 맞추었지만, 조금 더 클린한 코드를 위해 다듬어야겠다는 생각이 들었다. 

좌표가 유효한 주소인가 확인하는 것, 각 케이스를 나누어 케이스마다 함수를 만드는 것, 그리고 좌표를 출력시키는 것

크게 3부분으로 나누어, 더 클린한 코드를 만들어서 다음에 다시 시도해보아야 겠다.