[백준(BOJ)] 14940번: 쉬운 최단거리 (C++)

2는 하나만 있으므로, 입력받을 때 2 좌표를 저장한다.

void search(int x, int y,int num){
    queue< pair<int,int> > q;
    q.push(make_pair(x,y));
    visited[x][y]=1;
    answer[x][y]=num;
    while(!q.empty()){
        int cx=q.front().first;
        int cy=q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];
            // 0이면 방문하지 못함
            if(nx<0 || ny<0 || nx>n || ny>m || graph[nx][ny]==0) continue;
            if(!visited[nx][ny]){
                visited[nx][ny]=1;
                
                answer[nx][ny]=answer[cx][cy]+1;
                //cout << "answer " << nx << ", " << ny << ": " << answer[nx][ny] << endl;
                q.push(make_pair(nx,ny));
            }
        }        
    }

}

해당 좌표를 answer[x][y]=0으로 하고, 해당 좌표 기준 (-1,0), (0,-1), (1,0), (0,1) 위치의 좌표가 유효하다면 answer[next_x][next_y]=answer[x][y]+1;을 하고 각 좌표를 queue에 push하여 이후에 해당 좌표 근처를 체크할 수 있게 한다.

이때 0인 값일 때는 방문하지 않는다.

    for(int i=0; i<n;i++){
        for(int j=0; j<m; j++){
            if(visited[i][j]) {
                cout << answer[i][j] << " ";
            }
            else {
                if(graph[i][j]==0) cout << 0 << " ";
                else cout << -1 << " ";
            }
        }
        cout << endl;
    }

방문했으면 0이 아닌 경우이므로 answer을 출력하고, 방문하지 못했으면 0인 값이거나 0인 값 주변 좌표인 것이다.

따라서 입력했을 때 0이었으면 0을 출력하고, 아닌 경우 -1을 출력한다.

 

📝 전체 코드

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int graph[1000][1000];
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int visited[1000][1000];
int answer[1000][1000];
int n,m;

void search(int x, int y,int num){
    queue< pair<int,int> > q;
    q.push(make_pair(x,y));
    visited[x][y]=1;
    answer[x][y]=num;
    while(!q.empty()){
        int cx=q.front().first;
        int cy=q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];
            // 0이면 방문하지 못함
            if(nx<0 || ny<0 || nx>n || ny>m || graph[nx][ny]==0) continue;
            if(!visited[nx][ny]){
                visited[nx][ny]=1;
                
                answer[nx][ny]=answer[cx][cy]+1;
                //cout << "answer " << nx << ", " << ny << ": " << answer[nx][ny] << endl;
                q.push(make_pair(nx,ny));
            }
        }        
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tx,ty;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> graph[i][j];
            if(graph[i][j]==2){
                tx=i; ty=j;
            }
        }
    }
    int num=0;

    search(tx,ty,0);

    for(int i=0; i<n;i++){
        for(int j=0; j<m; j++){
            if(visited[i][j]) {
                cout << answer[i][j] << " ";
            }
            else {
                if(graph[i][j]==0) cout << 0 << " ";
                else cout << -1 << " ";
            }
        }
        cout << endl;
    }    
    

    return 0;
}

 

✅ 제출 결과