[백준] 14940번 쉬운 최단거리 JAVA (자바) 풀이

문제 14940번 (bfs)

 :  모든 지점에 대해서 목표지점까지의 거리를 구해라

   

 :  가로와 세로로만 움직일 수 있다

 

 

 [입력]

 :  첫째줄에 지도 세로 n, 가로 m ( 2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000 )

 :  다음 n개의 줄에 m개의 숫자 ( 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점)

 

 

[출력]

 :  각 지점에서 목표지점까지의 거리를 출력

    (원래 갈 수 없는 땅인 위치는 0 / 목표까지 도달할 수 없는 위치는 -1 출력)

 

[설명]

 

1. 시작지점을 목표지점으로 잡기

• 각 노드에서 목표지점으로 가는 것을 계산하려면 복잡
• 목표지점부터 시작하면 가는 노드마다 거리가 기록됨 (간편)

 

2. 출력은 3가지

• 값이 0이거나 2인 지점은 애초에 움직일 수 없기 때문에 0 출력
• 값이 1이지만 사방이 막혀 이동할 수 없다면 -1 출력
  • arr 1 임에도 불구하고 조건에 맞지않아서 방문처리가 안됐는지 확인
• 나머지는 bfs 돌리면 결과나오기 때문에 count 배열 출력
  

 

3. int count가 아닌 count 배열 이용

 [코드]

import java.io.*;
import java.util.*;
import java.awt.*;
public class Main{
    static int dx[]={0,0,1,-1};
    static int dy[]={1,-1,0,0};
    static int arr[][],m,n,end,count[][],a,b;
    static boolean visit[][];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m=Integer.parseInt(st.nextToken());
        n=Integer.parseInt(st.nextToken());
        arr=new int[m][n];
        visit=new boolean[m][n];
        count=new int[m][n];
        
        for(int i=0; i<m;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());
                if(arr[i][j]==2){
                     a=i;
                     b=j;
                }
            }
        }
        
        bfs(a,b);
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j]==0||arr[i][j]==2){
                    System.out.println("0 ");
                }
                else if(!visit[i][j]&&arr[i][j]==1){
                    System.out.println("-1 ");
                }
                else{
                    System.out.println(count[i][j]+" ");
                }
            }
            System.out.println();
        }
    }
    
    static void bfs(int x, int y){
        Queue<Point> q=new LinkedList<>();
        q.add(new Point(x,y));
        visit[x][y]=true;
        
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0; i<4;i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(0<=nx&&nx<m && 0<=ny&&ny<n && arr[nx][ny]==1&&!visit[nx][ny]){
                    visit[nx][ny]=true;
                    q.add(new Point(nx,ny));
                    count[nx][ny] = count[p.x][p.y]+1;
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int dx[]={0,0,1,-1};  가로 세로 이동가능
    static int dy[]={1,-1,0,0};  가로 세로 이동가능
    static int arr[][],m,n,end,count[][],a,b;
    static boolean visit[][];

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    m=Integer.parseInt(st.nextToken());  가로
    n=Integer.parseInt(st.nextToken());  세로
    arr=new int[m][n];  입력 배열
    visit=new boolean[m][n];  방문 배열
    count=new int[m][n];  결과 출력용 배열
        
 :  for(int i=0; i<m;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());  배열 입력받기
                if(arr[i][j]==2){  목표지점 좌표 미리 저장해두기
                     a=i;
                     b=j;
                }
            }
    }
        
 :  bfs(a,b);  목표지점부터 시작
        
 :  for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j]==0||arr[i][j]==2){  배열 0이거나 2면 못감 
                    System.out.println("0 ");  0출력
                }
                else if(!visit[i][j]&&arr[i][j]==1){  bfs에서 arr가 1이라 갈 수 있는데도 visit이 false라면
                    System.out.println("-1 ");  -1출력
                }
                else{
                    System.out.println(count[i][j]+" ");  나머지는 count 배열 출력
                }
            }
            System.out.println();  행마다 개행
    }
   
   

 :  static void bfs(int x, int y){
        Queue<Point> q=new LinkedList<>();  큐선언
        q.add(new Point(x,y));  목표지점 좌표 큐에 추가
        visit[x][y]=true; 방문처리
        
        while(!q.isEmpty()){
            Point p = q.poll();  큐에서 좌표 뽑기
            for(int i=0; i<4;i++){
                int nx = p.x+dx[i];  이동한 새 x좌표
                int ny = p.y+dy[i];  이동한 새 y좌표
                if(0<=nx&&nx<m && 0<=ny&&ny<n && arr[nx][ny]==1&&!visit[nx][ny]){  조건에 부합하면
                    visit[nx][ny]=true;  방문처리                                                                             
                    q.add(new Point(nx,ny));  큐에 추가
                    count[nx][ny] = count[p.x][p.y]+1;  거리 저장
                }
            }
        }
    }

   

 

      

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *