https://www.acmicpc.net/problem/14940
14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
이 문제는 전형적인 bfs문제이다 일단 예시로 주어지는 그림부터가 이문제는 bfs로 푸는 것이다라고 알려주고 있다. 이에 이문제는 bfs로 풀어주면 된다 bfs 문제는 queue를 많이 사용한다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int arr[1002][1002] = { 0,};
int answer[1002][1002] = {0,};
int startX, startY;
queue <pair<int,int>> bfsq;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
int temp;
cin >> temp;
arr[i][j] = temp;
if (temp == 2) {
startX = i;
startY = j;
}
}
}
bfsq.push(make_pair(startX, startY));
answer[startX][startY] = 0;
while (!bfsq.empty()) {
startX = bfsq.front().first;
startY = bfsq.front().second;
bfsq.pop();
if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
bfsq.push(make_pair(startX, startY + 1));
answer[startX][ startY + 1] = 1 + answer[startX][startY];
}
if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
bfsq.push(make_pair(startX, startY - 1));
answer[startX][startY - 1] = 1 + answer[startX][startY];
}
if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
bfsq.push(make_pair(startX+1, startY));
answer[startX+1][startY] = 1 + answer[startX][startY];
}
if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
bfsq.push(make_pair(startX-1, startY));
answer[startX-1][startY] = 1 + answer[startX][startY];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (answer[i][j] == 0&& arr[i][j] == 1) {
cout << -1 << " ";
}
else {
cout << answer[i][j] << " ";
}
}
cout << endl;
}
}
전체 코드는 이렇게 되고 하나하나 설명을 하도록 하겠다.
bfsq.push(make_pair(startX, startY));
answer[startX][startY] = 0;
while (!bfsq.empty()) {
startX = bfsq.front().first;
startY = bfsq.front().second;
bfsq.pop();
if (arr[startX][startY + 1] == 1 && answer[startX][startY + 1] == 0) {
bfsq.push(make_pair(startX, startY + 1));
answer[startX][ startY + 1] = 1 + answer[startX][startY];
}
if (arr[startX][startY-1] == 1 && answer[startX][startY - 1] == 0) {
bfsq.push(make_pair(startX, startY - 1));
answer[startX][startY - 1] = 1 + answer[startX][startY];
}
if (arr[startX+1][startY] == 1 && answer[startX+1][startY] == 0) {
bfsq.push(make_pair(startX+1, startY));
answer[startX+1][startY] = 1 + answer[startX][startY];
}
if (arr[startX-1][startY ] == 1 && answer[startX-1][startY] == 0) {
bfsq.push(make_pair(startX-1, startY));
answer[startX-1][startY] = 1 + answer[startX][startY];
}
}일단 위 코드의 이부분은 pair로 이루어진 큐에서 값을 뽑고 그값을 기준으로 상하좌우의 값을 큐에다가 다시 넣어준다 그후 넣어준큐의 순서에대한 값이 저장되어있는 answer배열에 나의 방문번째수 +1을 넣어서 해준다 즉 내가 2번 layer에 자식이라면 나의 상하좌우는 3번 layer 에 자식이된다
트리로 그리게 되면 이런 구조가 된다. 그후 내가 몇번째 layer에 있는지를 answer배열에 저장해주면 된다.