Posts [백준] 1261번 - 알고스팟
Post
Cancel

[백준] 1261번 - 알고스팟


백준 온라인 저지의 1261번 알고스팟 문제입니다.

[링크] https://www.acmicpc.net/problem/1261


문제 조건과 설명

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.


Input

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

Output

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.


생각한 아이디어

(0,0) 부터 시작해, 맨 끝 (N-1,M-1) 까지 가는 최단 경로를 찾는 문제입니다.

이 문제는 상,하,좌,우 모두 갈 수 있기 때문에, dp 풀이가 불가능합니다. (dp는 아래나 오른쪽 방향으로 갈 때만 가능)

이 문제를 다익스트라로 접근해 보겠습니다.

이 문제에서는 모든 칸(정점)들 사이의 가중치는 1 아니면 0으로 보면 됩니다.

그래서 상, 하, 좌, 우 모두 이동하는데 칸의 값이 1일 때와 0일 때를 구분합니다.

기존의 다익스트라가 dist[next] > distance + graph(cur)(i).second 이런 식으로 다음에 갈 곳의 dist 배열 값이, 최소 거리 갖는 정점까지의 distance + 그 정점에서 다음에 갈 곳의 가중치보다 클 경우 dist[next] 값을 업데이트 하는 방식이었습니다.

지금은 모든 가중치가 0 아니면 1이고, 입력을 2차원으로 받았기 때문에 거리 배열도 2차원 배열 dist로 선언한다고 가정하겠습니다.

그러면 위의 코드가

1
2
// 다음 곳이 부수고 가야 하는 문, 즉 1이었을 때
dist[nextY][nextX] > dist[curY][curX] + 1

혹은

1
2
// 다음 곳이 그냥 갈 수 있는 빈 공간이었을 때
dist[nextY][nextX] > dist[curY][curX] + 0

으로 바뀌면 될 것입니다.

+1과 +0은 기존처럼 다음에 갈 그 정점 사이의 가중치로 생각하면 됩니다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

#define INF 987654321

using namespace std;

int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
int arr[101][101];
int dist[101][101];

queue<pair<int, int>> pq;

void dijkstra(int M, int N, int r, int c) {

	// 큐에 초기값 push
	pq.push({ r,c });
	// 초기 거리값 0으로 초기화
	dist[r][c] = 0;

	while (!pq.empty()) {
		int ry = pq.front().first; // curY
		int rx = pq.front().second; // curX
		pq.pop();

		for (int i = 0; i < 4; i++) {

			int ty = ry + dy[i]; //nextY
			int tx = rx + dx[i]; //nextX

			if (ty < 0 || ty >= N || tx < 0 || tx >= M) continue;

			// 부수고 가는 문이었을 때
			if (arr[ty][tx] == 1) {
				if (dist[ty][tx] > dist[ry][rx] + 1) {
					dist[ty][tx] = dist[ry][rx] + 1;
					pq.push({ ty,tx });
				}
			}
			// 빈 공간이었을 때
			else if (arr[ty][tx] == 0) {
				if (dist[ty][tx] > dist[ry][rx]) {
					dist[ty][tx] = dist[ry][rx];
					pq.push({ ty,tx });
				}
			}
		}
	}

}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int M, N;
	scanf("%d %d", &M, &N);
	// M이 열, N이 행

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[i][j]);
			dist[i][j] = INF;
		}
	}

	dijkstra(M, N, 0, 0);
	printf("%d", dist[N - 1][M - 1]);
	return 0;
}