[Silver I] 쉬운 최단거리 - 14940
성능 요약
메모리: 81452 KB, 시간: 664 ms
분류
너비 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2023년 12월 12일 10:15:01
문제 설명
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
풀이 방법
1. 값을 읽어들일 때 시작점 위치를 기억해준다.
2. 1이라면 -1로 기록(방문하지 못한 곳은 -1로 처리해줘야하기 때문에)
3. 0이라면 그대로 기록
4. bfs로 방문한다.(bfs는 순차적으로 방문하기 때문에 처음 방문값이 최소값임)
5. 범위 밖이거나 Or 이미 방문했거나(-1이아닐 때) Or 벽일 때는 Continue;
6. 현재 위치에서 +1 하고 값 삽입하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] answer;
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();
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
answer = new int[a][b];
int[] start = new int[2];
for (int i = 0; i < a; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < b; j++) {
int tmp = Integer.parseInt(st.nextToken());
// 1아러묜 방문하지 못한 위치는 -1로 처리해야해서 미리 삽입
if (tmp == 1) {
answer[i][j] = -1;
}
// 시작점일 때 위치 기억
else if (tmp == 2) {
start[0] = i;
start[1] = j;
}
}
}
bfs(start);
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
sb.append(answer[i][j] + " ");
}
sb.append("\n");
}
System.out.println(sb);
}
private static void bfs(int[] start) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
int[] dirX = {0, 0, -1, 1};
int[] dirY = {-1, 1, 0, 0};
while (!queue.isEmpty()) {
// 현재 위치 기억
int[] cur = queue.poll();
// 상,하,좌,우순으로 확인하기
for (int i = 0; i < 4; i++) {
int nX = cur[0] + dirX[i];
int nY = cur[1] + dirY[i];
// nX, nY가 범위밖일 때는 Continue;
if (nX < 0 || nX >= answer.length || nY < 0 || nY >= answer[nX].length) {
continue;
}
// -1이 아니라면(벽이거나 방문했다면) continue;
if (answer[nX][nY] != -1) {
continue;
}
// 현재 위치 + 1로 최소값 삽입 후 큐에 넣어준다.
answer[nX][nY] = answer[cur[0]][cur[1]] + 1;
queue.offer(new int[] {nX, nY});
}
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 2659번 : 십자카드 문제 Silver3(실버3) - JAVA[자바] (0) | 2023.12.13 |
---|---|
[백준] 2630번 : 색종이 만들기 Silver2(실버2) - JAVA[자바] (0) | 2023.12.12 |
[백준] 10431번 : 줄세우기 Silver5(실버5) - JAVA[자바] (1) | 2023.12.11 |
[백준] 2331번 : 반복수열 Silver4(실버 4) - JAVA[자바] (1) | 2023.12.10 |
[백준] 4963번 : 섬의 개수 Silver2(실버 2) - JAVA[자바] (0) | 2023.12.10 |