[C언어] 백준 2206벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

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

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1 

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 

15

예제 입력 2 

4 4
0111
1111
1111
1110

예제 출력 2 

-1

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

2206번: 벽 부수고 이동하기

문제 풀기 전 로직 생각하기

---

맵의 좌상단에서 우하단까지의 최단 거리를 구하는 BFS 문제입니다.

조건이 하나 추가가 되었는데 벽을 하나 무시하고 최단 거리를 구하는 것인데요.

 

visited 배열을 이용해서 "이 경로는 내가 벽을 부수고(부수지 않고) 지나온 길이야" 라고 인식 시키면 될 것 같습니다.

그리고 이동할 때 몇가지를 기억하면서 이동시켜야 할것 같습니다.

• 벽을 부수지 않고 이동했을 때 벽을 만난 경우 이동(이 때 벽을 부쉈다고 체크)
• 벽을 부수지 않고 이동했을 때 벽이 아닌 곳을 만난 경우 이동
• 벽을 부수고 벽이 아닌 곳을 만난 경우 이동
• 벽을 부수고 벽인 곳을 만났을 때 무시

이 네 가지를 생각하면서 로직을 짜면 좀 더 쉽게 구현할 수 있을 것 같네요!

 

전체 코드

---

#include <stdio.h>
#define MAX_SIZE 1001 * 1001 + 10
int n, m, map[1001][1001], temp[1001][1001] = {}, visited[1001][1001][2] = {};
int	dx[4] = {-1, 0, 1, 0};
int	dy[4] = {0, 1, 0, -1};
typedef struct
{
	int	y;
	int	x;
	int	wall;
}	queue;

queue	q[MAX_SIZE];

void	bfs()
{
	int	x, y, nx, ny, wall, cur = -1, last = 0;

	q[last].x = 0;
	q[last].wall = 0;
	q[last++].y = 0;
	while (++cur < last && temp[n - 1][m - 1] == -1)
	{
		x = q[cur].x;
		y = q[cur].y;
		wall = q[cur].wall;
		for (int i = 0; i < 4; i++)
		{
			nx = x + dx[i];
			ny = y + dy[i];
			if (0 <= nx && nx < m && 0 <= ny && ny < n)
			{
            	// 벽을 부수지 않았는 데 벽을 만난 경우
				if (map[ny][nx] == 1 && wall == 0 && !visited[ny][nx][wall + 1])
				{
					temp[ny][nx] = temp[y][x] + 1;
					q[last].y = ny;
					q[last].x = nx;
					q[last++].wall = 1;
					visited[ny][nx][wall + 1]++;
				}
                // 벽이 아니면서 방문 한 적이 없는 경우 (wall이 0이든 1이든 상관 x)
				else if (map[ny][nx] == 0 && !visited[ny][nx][wall])
				{
					temp[ny][nx] = temp[y][x] + 1;
					q[last].y = ny;
					q[last].x = nx;
					q[last++].wall = wall;
					visited[ny][nx][wall]++;
				}
			}
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &map[i][j]);
			temp[i][j] = -1;
		}
	}
	temp[0][0] = 1;
	bfs();
	printf("%d\n", temp[n - 1][m - 1]);
	return (0);
}

 

문제 해설

---

2차원 배열 temp를 전부 -1로, 좌상단은 1로 초기화 해줍니다.

bfs함수의 가장 안쪽의 첫 번째 if 문을 보시면 벽을 만났을 때 지금 껏 벽을 부순적이 있는지를 wall 변수로 체크합니다.

이 wall 변수는 구조체 안에서 확인하게 했습니다.

벽을 부순적이 없는데 벽을 만난 경우 그 벽으로 이동할 수 있게 삽입 해주고 벽을 부순적이 있다고 큐에 wall 변수를 1로 초기화 해줍니다.

 

두 번째 if 문은 벽이 아닌곳을 만났을 때 방문한 적이 있는지 없는지 확인을 하는데요

이 때 wall 변수가 0이든 1이든 상관없습니다.

1이면 자연스럽게 visited[ny][nx][1]를 확인해서 벽을 부수고 이동했던 경로인지를 파악하기 때문이죠

0이면 그냥 이동해도 상관 없을 테고요

 

이런식으로 벽을 한번만 부수게끔 처리하면서 while로 큐가 빌 때까지 면서 우하단 방문 체크하기 전 까지 반복했습니다.

 

그 후 배열의 우하단을 출력하고 끝내는 방식으로 구현했습니다.