문제접근
•
목표지점의 좌표부터 시작하여 bfs
놓쳤던 부분
•
갈 수 있는 곳을 도달할 수 없는 경우 -1을 출력하기 위하여 애초에 answer를 -1로 초기화하고 업데이트 되지 못 하면 도달하지 못 했다는 뜻이라고 생각했는데, 애초에 0인 경우엔 0을 출력해야하는데 애초에 0인데 거기에 도달을 못 해서 -1로 찍히는 경우가 있었음
출력할때 원래가 0이거나 2이면 0을 출력하게 하면 됨
2 4
1 0 1 0
1 1 0 2
-1 0 -1 0
-1 -1 0 0
이어야 했는데
2 4
1 0 1 0
1 1 0 2
-1 -1 -1 0
-1 -1 0 0
이 출력되었었음
C++
복사
코드
4144 KB
48 ms
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int n, m;
vector<vector<bool>> visited;
vector<vector<int>> map;
vector<vector<int>> answer;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
void bfs(int row, int col)
{
queue<pair<int, int>> q;
q.push({row, col});
visited[row][col] = true;
answer[row][col] = 0;
while (!q.empty())
{
int currentRow = q.front().first;
int currentCol = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nextRow = currentRow + dy[i];
int nextCol = currentCol + dx[i];
if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m)
continue ;
if (visited[nextRow][nextCol])
continue ;
if (map[nextRow][nextCol] == 1)
{
visited[nextRow][nextCol] = true;
q.push({nextRow, nextCol});
answer[nextRow][nextCol] = answer[currentRow][currentCol] + 1;
}
}
}
}
int main(void)
{
int targetRow;
int targetCol;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
map.resize(n, vector<int>(m));
visited.resize(n, vector<bool>(n, false));
answer.resize(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 2) {
targetRow = i;
targetCol = j;
}
}
}
bfs(targetRow, targetCol);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 2 || map[i][j] == 0) {
cout << "0 ";
} else {
cout << answer[i][j] << " ";
}
}
cout << "\n";
}
return (0);
}
C++
복사
