2178번 - 미로 탐색 C++

문제 설명

---

대표적인 BFS 문제

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

 

 

---

Tip

본 문제에서는 그래프 입력이

101111
101010
101011
111011

이런식으로 붙어있어서 하나씩 떼어줘야 합니다.

문자열로 받아 한글자씩 떼는 방법도 있지만 매우 간단한 방법이 존재합니다.

 

scanf("%1d", &maze[i][j])

보통 C언어에서 입력값을 받을 때 사용하는 std::scanf 함수를 이용하는 것 입니다.

1d라는 것은 붙어있는 여러 개의 숫자를 한 글자씩 떼어 입력합니다.

(2d라면 두 개씩 끊어 입력합니다.)

---

 

BFS란?

https://yhoons.tistory.com/9

BFS(너비 우선 탐색) 알고리즘

 

---

코드

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

std::vector<std::vector<int>> maze; //N*M미로
std::queue<std::pair<int, int>> q; //방문큐
int N, M;

//탐색방향
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int BFS(int x, int y)
{
	q.push(std::make_pair(x,y)); //방문할 칸 푸쉬

	while(!q.empty())
	{
        //탐색할 칸 초기화
		x = q.front().first; 
		y = q.front().second;	
		q.pop(); //x, y 초기화 했으므로 큐에서 제거
     
	    for(int i=0; i<4; i++)
		{
			int next_x = dx[i] + x;
			int next_y = dy[i] + y;
			
            //예외처리
			if(next_x < 0 || next_x > N-1 || next_y < 0 || next_y > M-1)
			    continue;
			if(maze[next_x][next_y] == 0)
				continue;
			
            //방문 가능할 때
			if(maze[next_x][next_y] == 1)
			{
				maze[next_x][next_y] = maze[x][y] + 1; //누적 거리
				q.push(std::make_pair(next_x, next_y)); //칸 이동
			}
			
		}
	}
	return maze[N-1][M-1]; //마지막 칸 누적 거리 리턴
}


int main()
{

	std::cin >> N >> M;
	
	maze.resize(N+1, std::vector<int>(M+1, 0));
	
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<M; j++)
		{
			std::scanf("%1d", &maze[i][j]); 
		}
	}
	
    
	std::cout << BFS(0, 0);
	
	return 0;
}