lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이 문제는 너비 우선 탐색인 BFS를 이용해 풀 수 있는 문제이다.


아이디어 도출

BFS 문제를 여러 번 풀어봤다면 어떤 식으로 문제 해결을 할 수 있을지 금방 알 수 있을 것이다! 풀이를 위한 아이디어는 다음과 같다.

  1. 도달할 수 없는 땅의 위치(-1)일 경우 -1로 갱신하기 위해 미리 새로운 배열의 모든 원소를 -1로 초기화한다.
  2. 기존 지도를 입력받으며 갈 수 없는 땅의 위치(0)와 목표 지점 2의 위치(2)일 경우 0으로 먼저 갱신한다.
  3. 그리고 목표 지점 2의 위치를 구하고 2의 위치부터 BFS 함수를 통해 너비 우선 탐색을 진행한다.
  4. 지도의 위치별로 2로부터의 거리를 갱신하기 위해 새로운 배열에 이동거리를 갱신한다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

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

class Main {    
    
    // 상,하,좌,우로 탐색하기 위한 dx,dy 배열
    static int[] dx = new int[]{1, 0, -1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};

    // 위치를 입력받을 기존 지도와 이동거리를 기록할 새로운 지도 배열 선언
    static int[][] arr;
    static int[][] result;

    // 방문 배열 선언
    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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        result = new int[N][M];
        visited = new boolean[N][M];

        // 도달할 수 없는 땅의 위치를 구하기 위해 새로운 지도의 모든 원소를 미리 -1로 설정해둔다.
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                result[i][j] = -1;
            }
        }

        // 목표 지점 2의 위치를 구하기 위한 좌표 변수
        int x = 0;
        int y = 0;

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                
                arr[i][j] = Integer.parseInt(st.nextToken());
                
                // 목표 지점 2의 위치를 구하고 새로운 지도에 해당 위치를 갱신한다.
                if(arr[i][j] == 2) {
                    result[i][j] = 0;
                    x = i;
                    y = j;
                }
                
                // 새로운 지도에 갈 수 없는 땅의 위치(0)을 갱신한다.
                if(arr[i][j] == 0) {
                    result[i][j] = 0;
                }

            }
        }

        // BFS 함수를 통해 기존 지도를 탐색하며 새로운 지도에 목표 지점을 기준으로 이동거리를 갱신한다.
        BFS(x, y);

        for(int[] arr : result) {
            for(int num : arr) {
                bw.write(num+" ");
            }
            bw.write("\n");
        }
        
        bw.close();
        br.close();
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<4; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(isRange(i, j)) {
                    if(!visited[i][j] && arr[i][j] != 0) {
                        visited[i][j] = true;
                        q.offer(new int[]{i, j});
                        // 새로운 지도에 목표지점으로부터 현재 위치까지의 이동거리를 갱신한다.ㅁ
                        result[i][j] = result[now[0]][now[1]]+1;
                    }
                }
            }
        }
    }

    static boolean isRange(int x, int y) {
        if(0<=x && 0<=y && x<N && y<M) {
            return true;
        }
        return false;
    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy