BFS 두 문제

미로 탐색 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	192 MB	62619	22706	14445	35.210%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력

4 6

101111

101010

101011

111011

예제 출력

15

 

 

코드

#include 
#include 
#include 

int map[101][101];
std::queue<std::pair<int,int>> que;
int n = 0, m = 0;
int dist = 0;


void BFS()
{
	que.push(std::pair<int, int>(1, 1));
	dist++;
	while (!que.empty())
	{		
		int size = que.size();

		for (int ii = 0; ii < size; ii++)
		{
			std::pair<int, int> pair = que.front();
			que.pop();
			int row = pair.first;
			int col = pair.second;
			map[row][col] = 0;

			if (row == n && col == m)
				std::cout << dist << std::endl;

			if (map[row - 1][col] == 1) //up
			{
				map[row - 1][col] = 0;
				que.emplace(std::pair<int, int>(row - 1, col));
			}
			if (map[row + 1][col] == 1) //down
			{
				map[row + 1][col] = 0;
				que.emplace(std::pair<int, int>(row + 1, col));
			}
			if (map[row][col - 1] == 1) //left
			{
				map[row][col - 1] = 0;
				que.emplace(std::pair<int, int>(row, col - 1));
			}
			if (map[row][col + 1] == 1) //right
			{
				map[row][col + 1] = 0;
				que.emplace(std::pair<int, int>(row, col + 1));
			}
		}

		dist++;
		
	}
}

int main()
{
	
	std::cin >> n >> m;

	for (int ii = 1; ii <= n; ii++)
	{
		std::string str;
		std::cin >> str;
		for (int j = 1; j <= m; j++)
		{
			map[ii][j] = str[j - 1] - '0';
		}
	}

	BFS();

}

 

숨바꼭질 성공 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	69336	18873	11747	24.675%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 

5 17

예제 출력

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

코드

#include 
#include 
#include 

//int* visit;
//int* road;
int visit[100001];
std::queue que;
int sec = 0;

void BFS(int SuzinPos, int DestPos)
{
	que.push(SuzinPos);

	while (!que.empty())
	{
		int size = que.size();
		for (int ii = 0; ii < size; ii++)
		{
			int pos = que.front();
			que.pop();

			if (pos == DestPos)
			{
				std::cout << sec;
				return;
			}

			if (pos - 1 >= 0 && visit[pos - 1] == 0)
			{
				visit[pos - 1] = 1;
				que.push(pos - 1);
			}
			if (pos + 1 <= 100001 && visit[pos + 1] == 0)
			{
				visit[pos + 1] = 1;
				que.push(pos + 1);
			}
			if (pos * 2 <= 100001 && visit[pos * 2] == 0)
			{
				visit[pos * 2] = 1;
				que.push(pos * 2);
			}
		}

		sec++;
	}


}


int main()
{
	int N, K;
	std::cin >> N >> K;
	BFS(N, K);
}

 

 

간단한 DFS 두문제에 이어 간단한 BFS 두 문제

간단한 문제인데도 한달동안 까먹어서 많이 버벅였다.

DFS/BFS는 패턴이 비슷해서 자주자주 봐둬서 체화하면 잊어버리지 않을 것 같다.