/<> 백준 14940번 : 쉬운 최단거리 (C언어)

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

 

 

좌표의 값이 2인 점을 시작점으로 설정하고(거리 = 0) 이를 기준으로 BFS를 사용하여 좌표의 값이 1인 점의 거리를 1씩 늘려줍니다. 큐를 이용하여 BFS를 진행하면 됩니다. 저는 큐의 원소로 행 값과 열 값을 동시에 보유하는 구조체를 만들어 저장했습니다.

 

탐색을 통해 도달할 수 없는 지점은 거리를 -1로 설정해야 합니다. 이 조건을 못보고 처음에 왜 틀렸지 하면서 고민했었습니다... 도달할 수 없는 지점을 확인하는 방법은 마지막에 출력을 할 때, 값이 1이지만 방문하지 못한 좌표를 확인하면 됩니다.

 

 

<코드>

#include <stdio.h>

int n, m, startX, startY;
int map[1000][1000];
int visit[1000][1000] = {0,};
int distance[1000][1000];

int move_x[4] = {1, -1, 0, 0};
int move_y[4] = {0, 0, 1, -1};

typedef struct pos {
        int x;
        int y;
} pos;
int front = 0, rear = 0;

pos position[10000001];

void bfs() {
        while(front < rear) {
                int currX = position[front].x;
                int currY = position[front++].y;
                for(int i = 0; i < 4; i++) {
                        int newX = currX + move_x[i];
                        int newY = currY + move_y[i];
                        if(newX >= 0 && newX < n && newY >= 0 && newY < m && visit[newX][newY] == 0 && map[newX][newY] == 1) {
                                visit[newX][newY] = 1;
                                distance[newX][newY] = distance[currX][currY] + 1;
                                position[rear].x = newX;
                                position[rear++].y = newY;
                        }
                }
        }
        return;
}

int main() {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        scanf("%d", &map[i][j]);
                        if(map[i][j] == 2) {
                                startX = i; // 새로
                                startY = j; // 가로
                                visit[i][j] = 1;
                                distance[i][j] = 0;
                                position[rear].x = i;
                                position[rear++].y = j;
                        }
                }
        }

        bfs();

        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        if(map[i][j] == 1 && visit[i][j] == 0) printf("-1 ");
                        else printf("%d ", distance[i][j]);
                }
                printf("\n");
        }
        return 0;
}