[백준] CLASS3 14940 쉬운 최단거리 - JAVA [자바]

안녕하세요. 이번에는 백준 14940 쉬운 최단거리 문제를 풀어보려고 합니다.

 

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

14940번: 쉬운 최단거리

---

Problem

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

사진 1. 문제

---

Solution

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

public class Main {
    
    static class Node {
        int x, y;
        
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int[][] map;
    static boolean[][] visited;
    static int n, m;
    static Queue<Node> q = new LinkedList<>();
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0}; 
    
    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[1001][1001];
        visited = new boolean[1001][1001];
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < m; j++) {
                int num = Integer.parseInt(st.nextToken());
                if(num == 2) {
                    q.offer(new Node(i, j));
                    map[i][j] = 0;
                    visited[i][j] = true;
                } else {
                    map[i][j] = num;
                }
            }
        }
 
        System.out.println(bfs());
    }
    
    static String bfs() {
        while(!q.isEmpty()) {
            Node node = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if(map[nx][ny] == 1 && !visited[nx][ny]) {
                        q.offer(new Node(nx, ny));    
                        map[nx][ny] = map[node.x][node.y] + 1;
                        visited[nx][ny] = true;
                    } 
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && map[i][j] == 1) {
                    sb.append("-1").append(" ");
                } else {
                    sb.append(map[i][j]).append(" ");
                }
            }
            
            sb.append("\n");
         }
        
        return sb.toString();
    }
}

 

 이번 문제는 BFS를 사용하면 쉽게 풀 수 있는 문제이다. 여기서 우리는 원래 갈 수 있는 땅인 부분 중 도달할 수 없는 위치는 -1 로 출력하기 위해서 visited를 통해서 방문 체크를 해줘야한다.

 

1. 원래 갈 수 있는 땅인 부분 중 도달할 수 없는 위치를 -1로 출력하기 위한 코드

StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
		if(!visited[i][j] && map[i][j] == 1) {
			sb.append("-1").append(" ");
		} else {
			sb.append(map[i][j]).append(" ");
		}
	}
            
	sb.append("\n");
}
        
return sb.toString();

 

2. BFS 전체 코드

 
    static String bfs() {
        while(!q.isEmpty()) {
            Node node = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if(map[nx][ny] == 1 && !visited[nx][ny]) {
                        q.offer(new Node(nx, ny));    
                        map[nx][ny] = map[node.x][node.y] + 1;
                        visited[nx][ny] = true;
                    } 
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && map[i][j] == 1) {
                    sb.append("-1").append(" ");
                } else {
                    sb.append(map[i][j]).append(" ");
                }
            }
            
            sb.append("\n");
         }
        
        return sb.toString();
    }

---

Performance

사진 2. 실행 결과