쉬운 최단거리(14940)

쉬운 최단거리(14940)

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

public class Main {
  
  static int[][] map;
  static boolean[][] visited;
  static int n, m;
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
  
    StringTokenizer st =  new StringTokenizer(br.readLine());
    
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    map = new int[n+1][m+1];
    visited = new boolean[n+1][m+1];
    
    Node node = new Node();
    
    // map 입력
    for(int i = 1; i <= n; i++) {
      st = new StringTokenizer(br.readLine());
      
      for(int j = 1; j <= m; j++) {
        int num = Integer.parseInt(st.nextToken());
        map[i][j] = num;
        // 시작점 체크
        if(num == 2) {
          node.x = i;
          node.y = j;
          visited[i][j] = true;
        }
      }
    }
    
    BFS(node);
    
    // 출력
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= m; j++) {

        // 방문을 안했는데 값이 1이면 못가는 곳
        if(!visited[i][j] && map[i][j] == 1) {
          map[i][j] = -1;
        }
        sb.append(map[i][j]).append(" ");
      }
      sb.append("\n");
    }

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void BFS(Node node) {
    Deque<Node> dq = new ArrayDeque<>();
    
    dq.offerFirst(node);
    
    // 시작점의 값 0
    map[node.x][node.y] = 0;
    
    while(!dq.isEmpty()) {
      node = dq.pollLast();
      
      int x = node.x;
      int y = node.y;
      
      // 상
      if(x > 1 && !visited[x-1][y] && map[x-1][y] != 0) {
        map[x-1][y] = map[x][y] + 1;
        visited[x-1][y] = true;
        node = new Node(x-1, y);
        dq.offerFirst(node);
      }
      
      // 하
      if(x < n && !visited[x+1][y] && map[x+1][y] != 0) {
        map[x+1][y] = map[x][y] + 1;
        visited[x+1][y] = true;
        node = new Node(x+1, y);
        dq.offerFirst(node);
      }
      
      // 좌
      if(y > 1 && !visited[x][y-1] && map[x][y-1] != 0) {
        map[x][y-1] = map[x][y] + 1;
        visited[x][y-1] = true;
        node = new Node(x, y-1);
        dq.offerFirst(node);
      }
      
      // 우
      if(y < m && !visited[x][y+1] && map[x][y+1] != 0) {
        map[x][y+1] = map[x][y] + 1;
        visited[x][y+1] = true;
        node = new Node(x, y+1);
        dq.offerFirst(node);
      }
      
    }
  }
  
  public static class Node{
    int x;
    int y;
    
    public Node() {}
    
    public Node(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}

풀이과정

1. 도착 지점을 기준으로 멀어지게 되면 1씩 증가하는 것이기 때문에 BFS 방식으로 풀어야겠다고 계획하였다.
2. 도착 지점의 초기값이 2 이므로 도착지점을 BFS 메소드로 넣은 후 값을 0으로 변경하였다.
3. Queue를 이용하여 노드를 순차적으로 돌며 +1씩 하였다.
4. BFS 메소드 순회가 끝나고 출력 시에 map의 값이 1인데 방문도 안한 곳이면, 갈 수 없는 곳이므로 값을 -1로 변경 후 출력하였다.

- 성공
- 메모리 : 47688 KB
- 시간 : 700 ms

보안점

1. 다른 사람의 풀이를 참고해보니
2. map의 크기를 +2를 하여 입력받는 주변들을 0으로 감싸게 하였다.
3. BFS 메소드에서 순회 시 x축과 y축을 값을 증감 시키는 배열을 만들고
4. for문으로 돌며 상하좌우의 좌표를 Queue에 넣는 것을 보았다. for문을 쓰기 위해 map의 크기를 +2 한것 같다. 왜냐하면 범위를 벗어나게 되면 오류가 터지므로..
5. 그리고 나의 경우는 Node라는 클래스를 만들어 제너릭을 사용하였는데,
6. 다른 사람은 int[2]를 사용한 것을 보았다.
7. 생각해보면 Node 클래스에도 들어가는 필드 값은 int 2개이므로, int[2] 짜리를 만들어서 사용하는 것도 참고할만 하겠다.