morenow
morenow
morenow
전체 방문자
오늘
어제
  • 분류 전체보기 (83)
    • 스프링부트와 AWS로 혼자 구현하는 웹 서비스 (5)
    • [MSA] Spring Cloud로 개발하는 마이.. (14)
    • Baekjoon Online Judge (40)
    • Programmers (11)
    • Spring Boot (7)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Feign Client
  • Open Feign
  • write skew
  • JWT단점
  • dirty write
  • B+ Tree
  • HTTP Interface
  • 백준20058C++
  • lost update
  • 백준 파이어스톰
  • successHandler
  • jwt
  • Spring Boot
  • B Tree
  • HttpExchange
  • re-distribution
  • Id Token
  • copy up
  • Refresh Token Refresh
  • 마법사 상어와 파이어스톰

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
morenow

morenow

Baekjoon Online Judge

[BOJ] 14940 : 쉬운 최단거리 (Java)

2023. 11. 9. 02:21

 

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

 

14940번: 쉬운 최단거리

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이

www.acmicpc.net

걸린 시간 : 34분 33초


알고리즘

최단 거리 알고리즘 중 어떤 알고리즘?

최단 거리를 구할 수 있는 알고리즘 중 4가지를 살펴보자.

  어떤 한 시작점에서 출발할 경우 모든 시작점을 다 고려할 경우
가중치가 없는 경우 BFS 알고리즘 BFS or 플로이드 알고리즘
가중치가 있는 경우 다익스트라 알고리즘  플로이드 알고리즘

 

이렇게 4가지를 생각하면 어떤 문제에서 어떤 알고리즘을 써야할지 쉬울 것이다.

이 문제는 주변 칸까지의 거리가 모두 1이므로 가중치가 없다.

또한 도착점이 있지만, 역으로 생각해 도착점에서 모든 정점까지 거리를 구해도 되므로 한 시작점에서 시작한다고 생각해도 좋다.

따라서 BFS 알고리즘을 쓰자.

Pseudo Code

BFS의 대략적인 Pseudo Code는 다음과 같다.

board, dist, queue 선언 및 입력;
int di[], dj[] 선언;
dist배열을 모두 -1로 fill;
// 1. 시작점 처리
queue에 시작노드 삽입;
시작노드 dist를 0으로;
while (!q.empty()) {
	// 2. 현재 노드 처리
    int ci, cj = q.top();
    q.pop();
    for (int k = 0; k < 방향 가짓수; k++) {
        // 3. 다음 노드 처리
        int ni, nj = ci + di[k], cj + dj[k];
        // 4. 방문할 것인지
        if (ni와 nj가 범위안에 없다 || 갈 수 없는 곳(벽)이다 || 방문했다) continue; //여기서 방문했는지를 dist[ni][nj]가 -1인지로 체크
        // 5. 방문 처리
        큐에 nx, ny 삽입;
        dist[nx][ny] 최신화;
    }
}

 

하지만, 이 문제의 끝 조건때문에 이와 같은 코드를 사용할 수 없다. 즉, dist 배열로 방문체크를 할 수 없다.

vis 배열을 따로 만들어 방문체크를 해야 한다.

board, dist, visited, queue 선언 및 입력;
int di[], dj[] 선언;
// 1. 시작점 처리
queue에 시작노드 삽입;
시작노드 visited 체크;
while (!q.empty()) {
	// 2. 현재 노드 처리
    int ci, cj = q.top();
    q.pop();
    for (int k = 0; k < 방향 가짓수; k++) {
        // 3. 다음 노드 처리
        int ni, nj = ci + di[k], cj + dj[k];
        // 4. 방문할 것인지
        if (ni와 nj가 범위안에 없다 || 갈 수 없는 곳(벽)이다 || 방문했다) continue;
        // 5. 방문 처리
        visited에 [ni][nj] 방문처리;
        큐에 nx, ny 삽입;
        dist[nx][ny] 최신화;
    }
}

 

이런 코드는 굉장히 자주 나오기 때문에 툭 치면 나올 정도로 외운다.

위처럼 dist배열만을 사용할 땐 방문처리할 때 2가지 일(큐 삽입, 거리 최신화)을 하고, vis배열까지 사용할 땐 방문처리할 때 3가지 일(큐 삽입, 거리 최신화, 방문처리)을 한다.

맨 처음에 설정할 때는 반대로 dist배열만을 사용할 땐 3가지 일(dist배열을 -1로 fill, 시작점 큐 삽입, 시작점 dist를 0으로)을 하고, vis배열까지 사용할 땐 2가지 일(시작점 큐 삽입, 시작점 방문처리)만을 한다.

정답 코드

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 BOJ14940 {

    static int n, m;
    static int[][] board = new int[1001][1001];
    static int[][] dist = new int[1001][1001];
    static boolean[][] vis = new boolean[1001][1001];
    static int[] di = {-1, 0, 0, 1};
    static int[] dj = {0, -1, 1, 0};
    static Queue<Pos> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        Pos startPos = null;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 2) {
                    startPos = new Pos(i, j);
                }
            }
        }
        vis[startPos.i][startPos.j] = true;
        q.offer(startPos);
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            for (int k = 0; k < 4; k++) {
                Pos next = new Pos(cur.i + di[k], cur.j + dj[k]);
                if (next.i < 0 || next.i >= n || next.j < 0 || next.j >= m
                        || board[next.i][next.j] == 0 || vis[next.i][next.j])
                    continue;
                q.offer(next);
                vis[next.i][next.j] = true;
                dist[next.i][next.j] = dist[cur.i][cur.j] + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && dist[i][j] == 0) {
                    System.out.print(-1 + " ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    static class Pos {
        int i, j;

        Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

'Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 2805 : 나무 자르기 (C++)  (1) 2023.12.26
[BOJ] 9019 : DSLR (Java)  (0) 2023.11.09
[BOJ] 2630 : 색종이 만들기 (Java) with 분할 정복  (1) 2023.11.09
[BOJ] 1927 : 최소 힙 (Java)  (0) 2023.11.02
[BOJ] 11444 : 피보나치 수 6 (Java)  (0) 2023.11.02
    'Baekjoon Online Judge' 카테고리의 다른 글
    • [BOJ] 2805 : 나무 자르기 (C++)
    • [BOJ] 9019 : DSLR (Java)
    • [BOJ] 2630 : 색종이 만들기 (Java) with 분할 정복
    • [BOJ] 1927 : 최소 힙 (Java)
    morenow
    morenow

    티스토리툴바