[1261] 알고스팟(C++)

1. 문제

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

2. 접근 방법

1) (1,1) -> (N,M)으로 가는 모든 경우를 탐색해야 하므로 BFS / DFS로 구현

 

2) 문제에서 "부숴야 하는 벽의 최소 개수"를 구해야 하므로 단순 BFS / DFS에서 지금까지 깬 벽의 개수를 고려해야 함

 

3) 두 가지 경우의 수 

- DFS 형식으로 푸는 경우 : 재귀 + 배열을 사용하여 배열 map[N][M]에는 (1,1) -> (i,j)까지 도달 할 때 부순 벽의 최소 개수를 넣는다. 재귀를 통해 돌면서 기존 map[i][j]보다 해당 경로를 통해 부순 벽의 개수가 작으면 map[i][j]를 업데이트 하는 방식으로 진행한다.

 

- BFS 형식으로 푸는 경우 : BFS가 큐를 사용하므로, " 우선 순위 큐" 를 사용하여 (부순 벽의 개수, (좌표값) ) data를 넣는다. 큐의 top에는 항상 가장 적게 벽을 부쉈을 때의 좌표값을 나타내므로 q.top()을 꺼냈을 때 (N,M)이 최초로 나올 때 까지 bfs를 수행한다.

 

4) 나의 경우 BFS가 좀 더 편해서(고려해야 할 사항이 적어서 ) 우선순위 큐로 풀었다.

3. 실수했던 부분 & 처음 알았던 부분

1) 입력값을 받을 때 띄어쓰기가 없는 건 string으로 받기

  - 처음 int로 받았다가 입력값이 제대로 들어가지 않았음

  - int miro[N][M]  => string miro[N]; 후 for(int i=0; i <N;i++)으로 받기

 

2) 비교문 == 을 =로 처리했었음

  - 멍청이..

 

2) 고민했던 것

- visited 배열을 써야하는지 고민 : queue에서 pop한 후, 이미 방문처리를 했다는 것은 "최소 개수로 벽을 깬 상태"로 방문한 적이 있다는 것을 의미하므로 방문 처리를 해야 함

 

- 우선순위 큐 기준 : 당연히 "최소로 부신 벽의 개수"이므로 깬 벽의 개수를 queue의 가장 앞으로 넣을 것

 

- 우선수위 큐의 내용:  pair<int, pair<int,int> >으로 구현할 지, tuple<int,int,int> 으로 구현할지

직관적으로 내용을 의미하기엔 전자가 편하지만, 코테 같이 시간이 중요한 경우는 tuple로 바꿀 것

 

 

4. 코드

#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
#include<cstring>
#include<string>
#define MAX 101
using namespace std;


int main() {
	int N,M,answer;
	string miro[MAX];
	bool visited[MAX][MAX];
	memset(visited,false,sizeof(visited));
	pair<int,int> dir[4] = {{-1,0},{0,1},{1,0},{0,-1}};
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> >,greater<tuple<int,int,int> > > q;

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

	q.push(make_tuple(0,0,0));
	visited[0][0] = true;
    
	while(!q.empty()) {
		int cnt = get<0>(q.top());
		int cx = get<1>(q.top());
		int cy = get<2>(q.top());
		q.pop();

		if(cx == N-1 && cy == M-1) {
			answer = cnt;
			break;
		}
		
		for(int i=0;i<4;i++) {
			int nx = cx + dir[i].first;
			int ny = cy + dir[i].second;

			if(nx < 0 || nx >= N || ny <0 || ny>=M || visited[nx][ny] ) continue;
			visited[nx][ny] = true;
			 if(miro[nx][ny] == '1') q.push(make_tuple(cnt+1,nx,ny));
			else  q.push(make_tuple(cnt,nx,ny));
		}
	}
	cout <<answer<<endl;

	return 0;
}