[백준]2206. 벽 부수고 이동하기

문제 링크: problem-link

첫번째 풀이 시도 : 실패

전형적인 큐를 이용한 bfs 방식으로 접근했다. 하지만 문제 조건 중에, 이동 하는 중에 단 한 번 벽을 부수고 갈 수 있다고 되어 있다. 따라서 문제의 조건을 다음과 같이 적용했다.

1. 벽을 만나고 이 전에 이미 한 번 벽을 부수었다면 해당 좌표는 넘어간다.
2. 벽을 만났지만 아직 벽을 부수지 않았다면 해당 좌표를 큐에 넣어준다. 2-1. 벽의 좌표를 큐에 넣어줄 때 벽을 부수었는지 확인할 수 있는 정보를 함께 넣어준다.

나는 좌표 정보를 담을 수 있는 Point 클래스를 만들었고 이전 좌표가 벽을 부수고 왔는지 아닌지 확인할 수 있도록 boolean 타입의 isCrash 멤버 변수를 추가해주었다.

이를 구현한 코드는 다음과 같다.

for (int i = 0; i < 4; i++) {
    int nr = p.r + dr[i];
    int nc = p.c + dc[i];

    if (nr < 1 || nc < 1 || nr > N || nc > M) continue;
    if (visited[nr][nc]) continue;

    boolean isWall = (map[nr][nc] == 1);
    if (isWall && p.isCrash) continue; // 벽이고, 이미 다른 벽을 부수고 왔으면 건너뛴다.

    queue.add(new Point(nr, nc, p.depth + 1, isWall || p.isCrash));
}

테스트케이스 2개를 통과해서 채점을 했는데 ‘틀렸습니다’를 받았다. 다시 문제의 조건을 생각하면서 어디서 잘못되었는지 생각을 해본다.

두번째 풀이 시도 : 성공

내가 간과한 부분은 다음과 같다.

벽을 부수고 지나간 좌표는 벽을 부수지 않았을 때도 지나갈 수 있어야 한다.

따라서 벽을 부수고 지나온 경우와 벽을 부수지 않고 지나온 경우를 따로 체크하기 위해서 방문 배열을 따로 만들었다.

수정한 코드는 다음과 같다.

for (int i = 0; i < 4; i++) {
    int nr = p.r + dr[i];
    int nc = p.c + dc[i];

    if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

    boolean isWall = (map[nr][nc] == 1);
    if (isWall && p.isCrash) continue; // 벽이고 이미 다른 벽을 부수고 왔으면

    if (p.isCrash) { // 벽을 부수고 지나온 경우
        if (visitedCrash[nr][nc]) continue;
        visitedCrash[nr][nc] = true;
    } else { // 벽을 부수지 않고 지나온 경우
        if (visited[nr][nc]) continue;
        visited[nr][nc] = true;
    }

    queue.add(new Point(nr, nc, p.depth + 1, isWall || p.isCrash));
}

Github 링크: github-link