[백준/1261] 알고스팟

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/1261

1261번: 알고스팟

 

2) 설명

0(빈 공간), 1(벽)로 이루어진 미로가 있고 (1, 1)에서 (N, M)으로 도달하면서 1(벽)을 최소한으로 뚫고 갈 때, 뚫고 간 벽의 수를 구하는 문제.

2. 풀이

1) 알고리즘

    : 우선순위 큐, BFS

 

2) 풀이 설명

  처음에는 DFS를 사용하면 되겠다 생각했지만 BFS와 우선순위 큐를 사용하는 게 편하다고 생각했다.

일반적인 BFS문제를 풀듯이 풀었으나 큐 대신 우선순위 큐에 튜플( - 뚫은 벽의 수, x 좌표, y 좌표)를 넣어줬다.

우선순위 큐는 맥스 힙 방식(가장 큰 값부터 빼는 방식)으로 동작하기 때문에 뚫은 벽의 수를 음수처리 해줌으로써 가장 적게 벽을 뚫은 노드부터 빼오도록 했다.

 

ex) ㄱ : (-3, 2, 4)와 ㄴ : (-10, 3, 5)가 있으면 ㄱ은 벽을 3번, ㄴ은 벽을 10번 뚫은 것이고, 우선순위 큐에서는 -3 > -10 이기 때문에 ㄱ을 먼저 뽑는다.

 

즉 해당 노드를 처음 방문한다면 그 방문은 벽을 최소로 뚫는 경로로 방문한 것이 된다.

그러므로 BFS를 돌던 중 (N, M) 좌표를 방문한다면 바로 while문을 탈출하고 답을 내면 된다.

 

3. 코드

/*
	알고스팟
    BFS, Priority queue
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};

	int N, M, answer = -1;
	cin >> M >> N;
	
	vector<vector<char>> miro(N+1, vector<char>(M+1));
	vector<vector<bool>> visited(N+1, vector<bool>(M+1, false));

	priority_queue<tuple<int, int, int>> pq;

	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			cin >> miro[i][j];

	pq.push({0, 1, 1});
	visited[1][1] = true;

	while(!pq.empty()){
		int wall = get<0>(pq.top());
		int x = get<1>(pq.top());
		int y = get<2>(pq.top());
		pq.pop();
		
		if(x==N && y==M){
			answer = -wall;
			break;
		}
		for(int i=0;i<4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx<=0 || nx>N || ny<=0 || ny>M)
				continue;
			if(visited[nx][ny])
				continue;
			
			visited[nx][ny] = true;
			pq.push({(miro[nx][ny]=='1'? wall-1 : wall), nx, ny});
		}
	}
	
	cout << answer << endl;

	return 0;
}

 

 

4. 느낀점

 - 입력이 M, N 순서로 주어져서 일반적으로 생각하는 방식(N -> M)이랑 달라서 헷갈렸다.

 - visited를 안 써도 되지 않을까 잠시 생각했다. -> 무한루프 돌 수도 있다.

 - 인풋 한 줄을 한 글자씩 받아야 하는 걸 그냥 int로 받아버렸다. 입력 받기 신경쓰자.

 - 아직 tuple 사용법이 많이 미숙하다. 연습하자.