[boj] (g4) 2206 벽 부수고 이동하기

강신현·2022년 4월 13일

boj

[코딩테스트] 컴공선배 - 알고리즘 캠프

목록 보기

66/141

✅ BFS ✅ 최단거리

문제

링크

풀이

1. 문제 접근

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

처음에 이문제를 보고 위 조건 때문에 벽을 부수는게 경로가 짧아지는지 오히려 길어지는지 판단을 하고 나서 이동을 해야하나 생각했었다.
확인을 하기 위해서는 벽을 부순 경우와 부수지 않은 경우 모두 두가지 경우가 공통적으로 지나는 지점까지의 거리를 측정한 뒤에
다시 돌아와서 이동을 해야하는데 로직 자체가 효율적이지 않을 뿐더러 구현도 어려울 것 같았다.

결국 블로거 님들의 지혜를 빌려보니

이전에 3차원을 풀었던 것처럼 벽을 부순 경우와 부수지 않은 경우를 z 축처럼 추가하여 구현하는 방법이 있었다.
이렇게 되면 두가지 경우 모두 끝 지점까지 이동해보기 때문에
1. 중간에 벽을 부쉈는데도 또 벽이 나왔다거나 하는 상황에는 queue에서 pop이 되므로 이런 경우는 자연스럽게 제외가 되며
2. 벽을 부순 경우와 안부순 경우 뭐가 더 효율적인지는 그때 그때 비교할 필요 없이, 끝지점에 먼저 도착한 경우에 최단 거리를 출력하고 끝낼 것이기 때문에 비효율적인 경우는 끝까지 가보지도 못하고 종료된다. (고로 신경쓸 필요가 없어진다.)

BFS에서 queue를 이용하여 구현하기 때문에 가능한 것 같다.

2. 문제 해결 로직 (풀이법)

map[y][x][w] 이렇게 삼차원으로 구현할 건데 여기서 w는 벽을 부쉈는지 안부쉈는지의 경우를 구별하기 위함이다.

의사코드

string map[1001]
int dist[1001][1001][2] // 마지막 2는 벽을 부순경우 1, 안부순 경우 0
bool chace // 벽을 부술 수 있는 기회, 있으면 true, 없으면 false

dx[4] = {1, 0, -1, 0}
dy[4] = {0, 1, 0, -1}

struct idx{
	int x
    int y
    bool w // 벽을 부순경우(true), 부수지 않은 경우(false)
}
queue<idx> que

BFS(Y, X){
	que.push({Y,X,'false'})
    dist[Y][X][0] = 1
    dist[Y][X][1] = 1
    
    while(!que.empty){
    	x = que.front.x
        y = que.front.y
        w = que.front.w
        
        for(i : 0 ~ 3){
        	nx = x + dx[i]
            ny = y + dy[i]
            
            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue
            
            if(nx == M-1 && ny == N-1){
            	flag = true
                return
            }
            
            if(chace == false || map[ny][nx] == 0){ // 벽 부술 기회 이미 사용했거나 벽으로 막히지 않은 경우
            	dist[ny][nx][0] = dist[y][x][0] + 1 // 벽 안부숨
                map[ny][nx] = 1
            	que.push({ny,nx,false})
            }
            else{ // 부순 경우, 안부순 경우 둘 다 고려
            	dist[ny][nx][1] = dist[y][x][1] + 1 // 벽 부숨
                dist[ny][nx][0] = dist[y][x][0] + 1 // 벽 안부숨
                map[ny][nx] = 1
            	que.push({ny,nx,true})
            }
        }
    }
}

main(){
	cin >> N >> M
    
    for(i : 0 ~ N-1){
    	cin >> map[i]
    }
    
    BFS(0,0)
    
    if(flag == true) cout << dist[N-1][M-1][0]
    else cout << -1
}