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

2206번: 벽 부수고 이동하기

 

www.acmicpc.net

간단해 보이는 탐색 문제지만 상당히 고생을 한 문제다.

문제 설명을 보면

벽을 1회 부술 기회를 준다.

처음 구현했을 때, 시간 복잡도를 계산해보지 않고 벽들을 하나하나 백트래킹을 이용해 부수고 

BFS로 탐색을 진행했다.

당연히 시간초과

그 다음으로 구현을 했을 때 방문 체크시 이전 방문지에서 벽을 부수고 도달했는지 부수지 않고 도달했는지를 구조체 배열을 이용해 함께 체크를 해주었다.

또 여기서 문제 발견

이미 방문한 곳을 안가도록 해두었더니 벽을 뚫고 먼저 진행해버린 곳은 진행 불가

예외케이스 발생으로 틀렸다.

다시 분기를 생각해 본 결과

1. 현재 위치가 벽을 부수지 않고 도달한 경우

    1.1 다음 탐색을 할 곳이 방문하지 않은 곳이거나 벽을 부수고 도착한 곳일 경우

         1.1.1 다음 탐색할 곳이 길  --> 탐색 

         1.1.2 다음 탐색할 곳이 벽  --> 탐색(벽을 부순것을 체크)

    1.2 다음 탐색할 곳이 방문하지 않은 곳 --> 탐색 o

2. 현재 위치가 벽을 부수고 도달한 경우

   2.1 다음 탐색할 곳이 방문하지 않은 곳

         2.1.1 다음 탐색할 곳이 길 --> 탐색o

         2.1.2. 다음 탐색할 곳이 벽 --> 탐색x

 

이렇게 분기를 나눠 풀었다.

큐도 연결리스트를 이용해 간단히 구현하여 사용하였다.

/*2206번 벽 부수고 이동하기*/
#include <iostream>
using namespace std;
int N, M;
char Map[1001][1001];
int drc[] = { -1,0,1,0,0,1,0,-1 };//상 우 하 좌 탐색

typedef struct pnt { int r, c;}pnt;
typedef struct V { int visit; bool dstchk; }V;
V visit[1000][1000];
pnt temp;

typedef struct node {
	pnt value;
	struct node* next;
}node;

typedef struct queue {
	node *front, *rear;
	int len;
	queue() {
		front = rear = NULL;
		len = 0;
	}
}queue;

void Q_push(queue *Q, pnt value) {
	node *new_node = new node;
	new_node->value = value;
	new_node->next = NULL;
	if (Q->front == NULL) { // 큐가 비었을 때
		Q->front = new_node;
		Q->rear = new_node;
	}
	else {
		Q->rear->next = new_node;
		Q->rear = new_node;
	}
	Q->len++;
}

void Q_pop(queue *Q) {
	node *temp = Q->front;
	Q->front = Q->front->next;
	delete temp;
	Q->len--;
}

void BFS(int r, int c) {
	queue *Q = new queue;
	temp = { r,c };
	Q_push(Q, temp);
	visit[r][c] = { 1,false };
	while (Q->len > 0) {
		int cur_r = Q->front->value.r;
		int cur_c = Q->front->value.c;
		Q_pop(Q);
		for (int d = 0; d < 4; d++) {
			int nr = cur_r + drc[d];
			int nc = cur_c + drc[d + 4];
			if (!(nr < 0 || nc < 0 || nr >= N || nc >= M)) {
				if (visit[cur_r][cur_c].dstchk == true) {//현 위치까지 벽을 부수고 도착했다.
					if (visit[nr][nc].visit == 0) {//다음 갈 곳이 방문하지 않은 곳
						if (Map[nr][nc] == '0') {//다음 갈 곳이 길이다.
							visit[nr][nc].visit = visit[cur_r][cur_c].visit + 1;
							visit[nr][nc].dstchk = visit[cur_r][cur_c].dstchk;
							temp = { nr,nc };
							Q_push(Q, temp);
						}
						//여기선 이미 벽을 부수고 왔기 때문에 다음 갈 곳이 벽이면 갈 수 없다.
						else continue;
					}
				}
				else {//현 위치까지 벽을 부수지 않고 도착했다.
					if (!(visit[nr][nc].visit!=0 && visit[nr][nc].dstchk==false)) {
						if (Map[nr][nc] == '0') {//다음 갈 곳이 길이다.
							visit[nr][nc].visit = visit[cur_r][cur_c].visit + 1;
							visit[nr][nc].dstchk = visit[cur_r][cur_c].dstchk;
							temp = { nr,nc };
							Q_push(Q, temp);
						}
						else {//다음 갈 곳이 벽이다.
							visit[nr][nc].visit = visit[cur_r][cur_c].visit + 1;
							visit[nr][nc].dstchk = true;//벽 부수고 방문
							temp = { nr,nc };
							Q_push(Q, temp);
						}
					}
				}
				if (nr == N - 1 && nc == M - 1) return;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int r = 0; r < N; r++) cin >> Map[r];
	BFS(0, 0);
	if (visit[N - 1][M - 1].visit == 0) cout << -1;
	else cout << visit[N - 1][M - 1].visit;
}

 

도움이 되었던 예외 케이스

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

답 : 29