[백준/JAVA] 14940번: 쉬운 최단거리

🔺 문제

14940번: 쉬운 최단거리

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    
    static int n,m;
    static int[][] map, result;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(st.nextToken());   // 세로
        m = Integer.parseInt(st.nextToken());   // 가로
        
        map = new int[n][m];
        result = new int[n][m];
        visited = new boolean[n][m];
        
        int x = 0, y = 0;
        
        // 입력받기
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < m ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
 
                // 💥 목표 지점
                if(map[i][j] == 2) {
                    x = i;
                    y = j;
                }
                // 갈 수 없는 땅
                else if(map[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        
        // 🔔 목표 지점 기준 BFS 수행 🔔
        bfs(x, y);
        
        // 출력하기
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(!visited[i][j]) {
                    result[i][j] = -1;
                }
                sb.append(result[i][j] + " ");
            }
            sb.append("\n");
        }
       
        System.out.println(sb);
    }
    
    private static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)    continue;
 
                if(!visited[nx][ny] && map[nx][ny] == 1) {
                   visited[nx][ny] = true;
                   result[nx][ny] = result[now[0]][now[1]] + 1;
                    queue.add(new int[] {nx, ny});
                }
            }
        }
    }
}

 

 

✅ 해결 아이디어
✔ BFS

 

💥 유의사항

• bfs 수행할 때 nx, ny  조건문 범위 설정 잘 못하면.. 틀린다...

 

---

🔺 다른 풀이들

- 로직은 비슷한데 int[] 대신 Point 클래스 만들어 사용하심

[백준_14940번] 쉬운 최단거리

---

💬 느낀 점

디테일만 조금 잡으면 빨리 풀 수 있을 것 같다.

시간 단축하좌,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Baekjoon] 14940_쉬운 최단거리