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

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

14940번: 쉬운 최단거리

---

BFS를 사용하여 주변을 탐색하며 count+1 씩 해주면 될 것 같다.

 

1. 맵 초기화 진행
   1. 초기화 하면서 값이 2인 경우에는 시작점이므로 start 배열에 넣기
2. bfs에 start를 시작점으로 두기
   1. 큐 생성 하여 q.add(start)
   2. 큐에 넣었으니 방문 체크하기
   3. 시작점에 해당하는 맵은 0으로 값 바꾸기 (2 -> 0)
3. q가 빌 때까지 탐색하기
   1. 상,하,좌,우 탐색하며 유효한 위치(맵의 범위 이내, 방문 체크 false, 맵의 값이 0이 아님) 일 때 방문체크&q.add&맵 값+1
4. 탐색이 끝났다면 맵을 출력한다.
   1. 이 때, 0으로 막혀있어서 탐색을 못한 경우가 존재할 수 있으므로, 방문 여부는 false지만 값이 0이 아닌 경우는 -1로 출력한다. 

 

package yejin.song;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_쉬운최단거리 {
    static int N,M;
    static int map[][];
    static boolean visited[][];
    static int start[];
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];

        // 맵 초기화
        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) {
                    start = new int[]{i,j};
                }
            }
        }
        bfs(start);

        for (int i = 0 ; i< N; i++){
            for (int j = 0; j<M; j++){
                if (!visited[i][j] && map[i][j]==1){
                    System.out.print("-1 ");
                }
                else System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void bfs(int[] start){
        Queue<int[]> q = new LinkedList<>();
        visited[start[0]][start[1]] = true;
        map[start[0]][start[1]] = 0;
        q.add(start);

        while (!q.isEmpty()){
            int current[] = q.poll();
            int x = current[0];
            int y = current[1];

            for (int i =0 ; i<4; i++){
                int nx = dx[i] + x;
                int ny = dy[i] + y;

                if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && map[nx][ny]!=0){
                    map[nx][ny] = map[x][y] + 1;
                    visited[nx][ny] = true;
                    q.add(new int[]{nx,ny});
                }
            }
        }

    }
}

 

 

++ ) 4달 수 다시 풀었는데, 4배 정도 더 적은 시간에 풀었음. 

import java.util.*;
import java.io.*;

public class codingtest {
    static int map [][];
    static int score[][];
    static int N;
    static int M;
    static boolean visited[][];
    static Queue<int[]> q = new LinkedList<>();
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        score = new int[N][M];
        visited = new boolean[N][M];

        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) {
                    q.add(new int[]{i,j});
                    visited[i][j] = true;
                }
            }
        }

        bfs();

        StringBuilder sb = new StringBuilder();
        // 방문 못하고 || 0 아닌 곳은 -1로 바꾸기
        for(int i = 0 ; i < N; i++){
            for (int j = 0; j < M; j++){
                if (!visited[i][j] && map[i][j] == 1) score[i][j] = -1;
                sb.append(score[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());


    }

    public static void bfs(){

        while (!q.isEmpty()){
            int arr[] = q.poll();
            int current_x = arr[0];
            int current_y = arr[1];

            for (int i = 0; i < 4; i++){
                // 범위 안에 있는가
                // 방문 안했는가
                // 값이 1인가
                int search_x = current_x + dx[i];
                int search_y = current_y + dy[i];

                if (search_x < 0 || search_x >= N || search_y < 0 || search_y >= M) continue;
                if (visited[search_x][search_y]) continue;
                if (map[search_x][search_y] == 1){
                    visited[search_x][search_y] = true;
                    score[search_x][search_y] = score[current_x][current_y] + 1;
                    q.add(new int[]{search_x,search_y });
                }
            }
        }
    }



}