14940번: 쉬운 최단거리

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

14940번: 쉬운 최단거리

1. 문제 분석

2에서 부터 BFS

2. 코드 작성

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int map[1000][1000];
int check[1000][1000];
int ans[1000][1000];
queue<pair<int,int>> q;
int n, m;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int cnt = 0;
void bfs() {
	int y = q.front().first, x = q.front().second;
	check[y][x] = 1;
	ans[y][x] = cnt;
	while (q.empty() == 0)
	{
		cnt++;
		int queue_size = q.size();
		for (int j = 0;j < queue_size;j++)
		{
			y = q.front().first, x = q.front().second;
			q.pop();
			for (int i = 0;i < 4;i++)
			{
				int move_y = y + dy[i], move_x = x + dx[i];
				if (check[move_y][move_x] == 0 && move_x >= 0 && move_x < m && move_y >= 0 && move_y < n && map[move_y][move_x] == 1)
				{
					check[move_y][move_x] = 1;
					q.push({ move_y,move_x });
					ans[move_y][move_x] = cnt;
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	cin >> n >> m;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			cin >> map[i][j];
		}
	}
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			if (map[i][j] == 2)
			{
				q.push({ i,j });
 				bfs();
				break;
			}
		}
	}
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			if (map[i][j] == 1 && ans[i][j] == 0)
			{
				ans[i][j] = -1;
			}
		}
	}
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

3. 키워드

#BFS

4. 추가

bfs에서 n m 바꿔써서 93% 틀렸음 잘 보자....