문제
내용
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한 개다.
출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
문제 링크
14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
접근
목표 지점을 시작 지점이라고 생각하면 너비 우선 탐색을 통해 각 지점까지의 최단 거리를 구할 수 있다.
전체 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(
new OutputStreamWriter(System.out));
// 입력
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] g = new int[n][m];
boolean[][] visited = new boolean[n][m];
int[] start = null;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
g[i][j] = Integer.parseInt(st.nextToken());
if (g[i][j] == 2) {
start = new int[] { i, j };
}
}
}
// 거리 계산을 위한 너비 우선 탐색
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] { start[0], start[1], 0 });
visited[start[0]][start[1]] = true;
int[][] moves = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 },
{ 0, 1 }, };
while (queue.isEmpty() == false) {
int[] cur = queue.poll();
g[cur[0]][cur[1]] = cur[2];
for (int[] move : moves) {
int nextR = cur[0] + move[0];
int nextC = cur[1] + move[1];
int curD = cur[2];
// 올바른 좌표가 아닐
if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= m) {
continue;
}
// 갈 수 없는 땅일 때 (입력이 0으로 주어짐)
if (g[nextR][nextC] == 0) {
continue;
}
// 이미 방문처리 되었을 때 (이미 지나간 지점)
if (visited[nextR][nextC]) {
continue;
}
// 큐에 넣고 방문 처리
queue.offer(new int[] { nextR, nextC, curD + 1 });
visited[nextR][nextC] = true;
}
}
// 출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 방문을 하지 않은 지점
if (visited[i][j] == false) {
// 방문 x && 갈 수 없는 땅의 의미인 0
// (시작지점은 무조건 방문처리 되므로 예외)
if (g[i][j] == 0) {
bw.write(0 + " ");
}
// 방문 x && 원래 갈 수 있는 땅
else {
bw.write(-1 + " ");
}
}
// 방문한 지점
else {
bw.write(g[i][j] + " ");
}
}
bw.write("\n");
}
bw.close();
br.close();
}
}코드 분석
입력
// 입력
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] g = new int[n][m];
boolean[][] visited = new boolean[n][m];
int[] start = null;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
g[i][j] = Integer.parseInt(st.nextToken());
if (g[i][j] == 2) {
start = new int[] { i, j };
}
}
}문제 입력 조건에 맞게 입력을 받으면서 입력 값이 2일 때 즉, 목표 지점일 때 start 변수에 해당 좌표를 저장한다.
거리 계산을 위한 너비 우선 탐색
// 거리 계산을 위한 너비 우선 탐색
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] { start[0], start[1], 0 });
visited[start[0]][start[1]] = true;
int[][] moves = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 },
{ 0, 1 }, };
while (queue.isEmpty() == false) {
int[] cur = queue.poll();
g[cur[0]][cur[1]] = cur[2];
for (int[] move : moves) {
int nextR = cur[0] + move[0];
int nextC = cur[1] + move[1];
int curD = cur[2];
// 올바른 좌표가 아닐
if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= m) {
continue;
}
// 갈 수 없는 땅일 때 (입력이 0으로 주어짐)
if (g[nextR][nextC] == 0) {
continue;
}
// 이미 방문처리 되었을 때 (이미 지나간 지점)
if (visited[nextR][nextC]) {
continue;
}
// 큐에 넣고 방문 처리
queue.offer(new int[] { nextR, nextC, curD + 1 });
visited[nextR][nextC] = true;
}
}문제 조건에 가로와 세로로만 움직일 수 있다고 나와있으므로 moves 배열에 행과 열을 기준으로 움직일 수 있는 범위를 미리 정의해 놓고 반복문을 통하여 차례대로 방문한다.
방문을 하기 전에 아래의 조건을 확인 후 조건에 하나라도 맞는 것이 있다면 방문하지 않는다.
올바른 좌표가 아닐 때(인덱스가 벗어날 때)갈 수 없는 땅일 때(입력이 0으로 주어졌을 때)이미 방문처리 되었을 때(이미 지나간 지점일 때)
위 조건이 모두 거짓이라면 너비 우선 탐색을 위한 큐에 방문 좌표를 넣고, 방문 처리를 한다.
너비 우선 탐색을 하면서 방문을 할 때 입력받을 때 사용한 g 배열의 현재 좌표 부분을 목표 지점까지의 거리로 업데이트한다.
출력
// 출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 방문을 하지 않은 지점
if (visited[i][j] == false) {
// 방문 x && 갈 수 없는 땅의 의미인 0
// (시작지점은 무조건 방문처리 되므로 예외)
if (g[i][j] == 0) {
bw.write(0 + " ");
}
// 방문 x && 원래 갈 수 있는 땅
else {
bw.write(-1 + " ");
}
}
// 방문한 지점
else {
bw.write(g[i][j] + " ");
}
}
bw.write("\n");
}
bw.close();문제 출력 조건에 맞게 출력하는 부분이다.
방문 처리된 지점은 g 배열에 목표 지점까지의 거리가 저장되어 있으므로 그대로 출력한다.
방문 처리가 안된 지점은 원래 갈 수 없는 땅 인지, 원래 갈 수 있는 땅 인지 확인한 후에 0 혹은 -1을 출력한다.
후기
문제 이름 자체가 쉬운 최단거리인 것처럼 너비 우선 탐색의 기본 원리만 알면 쉽게 풀 수 있는 문제였던 것 같다.
