lango

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

2 minute read



문제 풀이

이번 문제는 너비 우선 탐색 BFS를 이용해 간단하게 풀 수 있다.


아이디어 도출

너비 우선 탐색인 BFS를 잘 숙지하고 있다면 쉽게 도연이가 사람들과 만난 횟수를 구할 수 있을 것이다.

문제풀이를 위한 아이디어는 다음과 같다.

  1. 지도를 입력받고 BFS 탐색을 수행한다.
  2. BFS로 탐색하면서 벽(X)이 아닌 빈공간(0)과 사람(P)일 경우만 상,하,좌,우 탐색을 이어나간다.
  3. 사람(P)을 만날 경우 만난 횟수를 1 증가시킨다.
  4. BFS 탐색 종료후, 만난 룃수가 1 이상이라면 만난 횟수를, 사람을 만나지 못했다면 “TT”를 출력한다.

유의할 점은 다음과 같다.

지도의 (0,0) 위치부터 탐색을 하는 것이 아니라, 도연이의 위치부터 탐색을 시작해야 벽을 고려하여 사람들과의 만난 횟수를 구할 수 있다.


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

작성코드

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

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

class Main {    

    static int[] dx = new int[]{1, 0, -1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};

    static boolean[][] visited;
    static char[][] map;

    static int N, M;

    static int result;

    public static void main(String[] args) throws IOException {

        try (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());

            map = new char[N][M];
            visited = new boolean[N][M];

            int x = 0;
            int y = 0;
            for(int i=0; i<N; i++) {
                String input = br.readLine();
                for(int j=0; j<M; j++) {
                    map[i][j] = input.charAt(j);
                    // 도연이의 위치를 x와 y에 담는다.
                    if(map[i][j] == 'I') {
                        x = i;
                        y = j;  
                    }
                }
            }
            
            // 만난 횟수를 담을 변수 초기화
            result = 0;

            // 도연이의 위치부터 BFS를 수행한다.
            BFS(x, y);
            
            // 만난 횟수가 1번 이상이라면 횟수를, 아니라면 "TT"를 출력한다.
            if(result > 0) {
                bw.write(result+"\n");
            } else {
                bw.write("TT"+"\n");
            }
            
        }

    }

    /**
     * BFS 탐색 함수
     * 벽(X)아닌 위치로 상,하,좌,우 탐색을 한다.
     * 탐색 중, 사람(P)의 위치일 경우 result를 1 증가시킨다.
     */
    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] && map[i][j] != 'X') {
                        visited[i][j] = true;
                        if(map[i][j] == 'P') {
                            result++;
                        }
                        q.offer(new int[]{i, j});
                    }
                }
            }
        }
    }
    
    static boolean isRange(int x, int y) {
        if(0<=x && 0<=y && x<N && y<M) {
            return true;
        }
        return false;
    }

}

출처

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

You may also enjoy