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

 

[BaekJoon] 2206번 벽 부수고 이동하기

 

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

 

 

내코드

 

- 정답률이 낮았던 이유가 있는 어려운 문제였다.

- 우선, queue에는 좌표값, 거리, 벽을 부쉈는지 아닌지 여부를 넣어주었다.

- 벽을 부수고 한 정점에 도착했느냐와 벽을 부수지 않고 도착했느냐가 다르기 때문에 visited배열에 벽을 부수고 왔는지/아닌지를 판별하기 위해 3차원으로 만들어주었다.

 

- 그 다음으로 bfs안에서 다음 칸을 queue에 넣어줄지 말지 생각하는 조건이 4가지로 나뉘어진다.

1. 다음칸이 벽인데 이미 벽을 부순경우

-> 진행 불가. queue에 넣지 않고 지나간다.

2. 다음칸이 벽인데 벽을 아직 안부순경우

->벽을 부쉈다는 표시를 해주고, queue에 넣어서 다음 단계로 간다.

3. 다음칸이 빈칸인데 이미 벽을 부순경우

-> visited[x][y][1] == false 즉, 해당 정점에선 아직 벽을 부순 경로가 지나가지 않았을 경우 queue에 넣는다.

4. 다음칸이 빈칸인데 벽을 아직 안부순경우

->  visited[x][y][0] == false 즉, 해당 정점에선 아직 벽을 안부순 경로가 지나가지 않았을 경우 queue에 넣는다.

 

#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <utility>

using namespace std;

const int MAX = 1001;
int n, m;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int arr[MAX][MAX] = { 0, };
bool visited[MAX][MAX][2];
struct Node {
	int x;
	int y;
	int distance;
	int wallDestroyed;
};
queue<Node> qu;

int bfs() {
	if (n == 1 && m == 1) return 1;
	qu.push({ 0,0,1,0 });
	visited[0][0][0] = true;

	while (!qu.empty()) {
		Node node = qu.front();
		qu.pop();
		if (node.x == n - 1 && node.y == m - 1) {
			return node.distance;
		}
		for (int i = 0; i < 4; i++) {
			int x = node.x + dx[i];
			int y = node.y + dy[i];

			if (x < 0 || y < 0 || x >= n || y >= m) continue;
			if (arr[x][y] == 0 && visited[x][y][node.wallDestroyed] == false) {
				qu.push({ x, y, node.distance + 1, node.wallDestroyed });
				visited[x][y][node.wallDestroyed] = true;
			}
			else if (arr[x][y] == 1 && node.wallDestroyed == 0) {
				qu.push({ x,y,node.distance + 1, node.wallDestroyed + 1 });
				visited[x][y][node.wallDestroyed + 1] = true;

			}
		}
	}
	return -1;
}

int main(void)
{
	//ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	cout << bfs();
	
	return 0;
}

 

2021.10.07 python으로 다시 품

- 문제 자체는 빠르게 이해하고 구현하였으나 백준 채점중 11퍼센트에서 계속 틀렸는데 틀린부분은 다음과 같다.

- visited 처리를 해줄 때 벽은 깬 경우와 아직 깨지 않은 경우를 나눠서 처리해줘야 했다.

- 각각에 대한 최단 경로가 다르기 때문

# BaekJoon2206.py
from collections import deque


N, M = map(int, input().split())
visited = [[[False for _ in range(2)] for _ in range(M)] for _ in range(N)]
arr = [[] for _ in range(N)]
for i in range(N):
    arr[i] = list(map(int, input()))
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
result = float('inf')


def bfs():
    global N, M, arr, dx, dy, result, visited

    queue = deque([[0, 0, False, 1]])  # x좌표, y좌표, 벽깬 여부, 거리
    visited[0][0][0] = True

    while queue:
        value = queue.popleft()

        # 마지막 칸에 도착한 경우
        if value[0] == N - 1 and value[1] == M - 1:
            result = min(result, value[3])

        for i in range(4):
            nx = value[0] + dx[i]
            ny = value[1] + dy[i]

            # 맵의 밖으로 나가는 경우 continue
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            if visited[nx][ny][value[2]]:
                continue
            # 벽인 경우
            if arr[nx][ny] == 1:
                # 아직 벽을 깨지 않은 경우
                if not value[2]:
                    queue.append([nx, ny, True, value[3] + 1])
                    visited[nx][ny][1] = True
                else:
                    continue
            # 벽이 아닌 경우
            if arr[nx][ny] == 0:
                queue.append([nx, ny, value[2], value[3] + 1])
                visited[nx][ny][value[2]] = True


bfs()

if result == float('inf'):
    print(-1)
else:
    print(result)

 

 

참고

https://yabmoons.tistory.com/73