[BOJ] 2178 미로탐색 (feat. bfs 알고리즘)

우선적으로 말씀드리자면 이 글은 문제를 분석하고 알고리즘을 설명하는 글이 아님을 밝힙니다.

저도 다른 게시글처럼 맛깔나게 정리해서 여러분들에게 도움이 되고 싶지만

그럼 포스팅 하는데 너무 오래 걸리기도 하고 또한 제 실력이 너무나도 부족합니다..(사실 이게 이유입니다 ㅎ..)

 

거두절미 하고

이 글을 쓰는 이유는 bfs 알고리즘을 처음 접해봤는데 너무 신세계라서 이 감각을 잊지 않기 위해서 오로지 저를 위해 작성합니당.

혹시나 2178 문제 또는 bfs 알고리즘을 공부하기 위해 이 글에 방문하신 거라면 제가 참고했던 블로그를 소개시켜드릴게요. 정말 깔끔하게 잘 정리되고 이해가 잘 되게 포스팅하셨더라구요

https://m.blog.naver.com/PostView.naver?blogId=jhc9639&logNo=222289089015&isFromSearchAddView=true

코드

---

 

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main()
{
	int m, n;
	cin >> n >> m;
	vector<vector<int>> miro(n, vector<int>(m, 0));
	vector<vector<int>> visited = miro;

	// 미로 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &miro[i][j]);
		} 
	}

	queue<tuple<int, int>> q;
	q.push({ 0, 0 });
	int cnt = 0;
	while (q.size())
	{
		int x, y, nx, ny;
		tie(y, x) = q.front();
		q.pop();
		for (int cnt = 0; cnt < 4; cnt++)
		{
			nx = x + dx[cnt];
			ny = y + dy[cnt];
			// 맵을 벗어난 좌표면 패스
			if (nx >= miro[0].size() || ny >= miro.size() || nx < 0 || ny < 0)
				continue;
			// 방문했던 곳이면 패스
			if (visited[ny][nx])
				continue;
			// 이동할 수 있다면
			if (miro[ny][nx])
			{
				q.push({ ny, nx });
				visited[ny][nx] = visited[ny - dy[cnt]][nx - dx[cnt]] + 1;		// 전에 있던 곳 + 누적 1
			}

		}
	}

	cout << visited[n - 1][m - 1] + 1<< endl;									// visited[0][0] = 0 이었기 때문에 + 1 해준다.
}

 

가장 놀라웠던 건 queue 의 pop 과 while문을 사용해 마치 재귀함수처럼 만들었던 것이에요 queue의 push로 좌표를 저장해두고 길이 막혀있다면 queue의 pop으로 지나왔던 좌표들로 되돌아 오고.

 

예전에는 이런 알고리즘들을 보면 숨이 턱턱 막혔어요. 내가 이런 알고리즘들을 생각할 수 있을까? 도저히 해낼 수 없다고 느낄 떄 벽을 느낀다고도 하잖아요. 그런데 요즘에는 조금은? 생각이 바꼈어요 이런 알고리즘들을 내 것으로 만들면 되지 않나? 그 과정은 매우매우매우 힘들겠지만 뭐, 죽기야 하겠어요? 노력해야죠ㅠㅠ

 

그래도 결국 알고리즘을 이해하고 저만의 코드로 만들면 나름 뿌듯하고 그 과정도 힘들지만 재미도 있더라구요. 

 

네. 끝입니다 같이 이런 것에 익숙해져요!