[백준/JAVA] 18428번: 감시 피하기

📖 문제

 

18428번: 감시 피하기

 

 

 

💡  풀이 방식

• 조합(DFS) + BFS

 

1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.

이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.

for(int i = 0 ; i < N ; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    for(int j = 0 ; j < N ; j++) {
        map[i][j] = st.nextToken().charAt(0);

        if(map[i][j] == 'S')      sList.add(new int[] {i, j});
        else if(map[i][j] == 'T') tList.add(new int[] {i, j});
        else if(map[i][j] == 'X') xList.add(new int[] {i, j});
    }
}

 

 

2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.

private static void dfs(int idx, int cnt) {
    // 장애물 3개 설치했을 때, 감시를 피할 수 있는지 확인
    if(cnt == 3) {
        bfs();
        return;
    }

    // xList에서 3개 뽑아서 장애물 설치
    for(int i = idx ; i < xList.size() ; i++) {
        if(!chk[i]) {
            chk[i] = true;
            dfs(i + 1, cnt + 1);
            chk[i] = false;
        }
    }
}

 

 

[모든 학생들이 감시 피할 수 있는지 확인하는 방법]

1) 뽑은 3개의 위치에 장애물을 설치한다.

for(int i = 0 ; i < chk.length ; i++) {
    if(chk[i]) {
        int x = xList.get(i)[0];
        int y = xList.get(i)[1];
        map[x][y] = 'O';
    }
}

 

2) 선생님 위치를 큐에 추가하고, 방문 처리한다.

for(int[] t : tList) {
    q.add(new int[] {t[0], t[1]});
    visited[t[0]][t[1]] = true;
}

 

3) 선생님 위치들에서부터 탐색하며 방문 처리를 진행한다.

4방향 탐색을 할건데, 이 때 뻗어나가며 격자 끝까지 전진할 것이므로 while문을 사용한다.

while(!q.isEmpty()) {
    int[] now = q.poll();

    for(int d = 0 ; d < 4 ; d++) {
        int nx = now[0] + dx[d];
        int ny = now[1] + dy[d];

        // 해당 방향으로 격자 끝까지 탐색
        while(nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if(map[nx][ny] == 'O')  break;  // 장애물 있으면 종료

            visited[nx][ny] = true;

            // 현재 이동 방향으로 이동 +1
            nx += dx[d];
            ny += dy[d];
        }
    }
}

 

 

4) 모든 학생들이 감시를 피할 수 있는지 (= 모든 학생들의 위치들이 미방문 된 상태) 확인한다.

그렇다면, YES를 출력하고 종료한다.

boolean isOK = true;    // 모든 학생들이 감시 피했는지 나타내는 변수
for(int[] s : sList) {
    if(visited[s[0]][s[1]]) {
        isOK = false;
    }
}

if(isOK) {  // 모든 학생들이 감시를 피했다면, YES 출력하고 종료
    System.out.println("YES");
    System.exit(0);
}

 

 

5) 장애물 설치했던 칸을 다시 빈 칸 X로 원상복구한다.

for(int i = 0 ; i < chk.length ; i++) {
    if(chk[i]) {
        int x = xList.get(i)[0];
        int y = xList.get(i)[1];
        map[x][y] = 'X';
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N;
    static char[][] map;
    
    static List<int[]> sList = new ArrayList<>();   // 학생 위치 리스트
    static List<int[]> tList = new ArrayList<>();   // 선생님 위치 리스트
    static List<int[]> xList = new ArrayList<>();   // 장애물 둘 수 있는 위치 리스트
    static boolean[] chk;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = st.nextToken().charAt(0);
                
                if(map[i][j] == 'S')      sList.add(new int[] {i, j});
                else if(map[i][j] == 'T') tList.add(new int[] {i, j});
                else if(map[i][j] == 'X') xList.add(new int[] {i, j});
            }
        }
        
        chk = new boolean[list.size()]; // 뽑았는지 여부
        dfs(0,0);
        
        System.out.println("NO");
    }
    
    
    private static void dfs(int idx, int cnt) {
        // 장애물 3개 설치했을 때, 감시를 피할 수 있는지 확인
        if(cnt == 3) {
            bfs();
            return;
        }
        
        // xList에서 3개 뽑아서 장애물 설치
        for(int i = idx ; i < xList.size() ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                dfs(i + 1, cnt + 1);
                chk[i] = false;
            }
        }
    }
    
    private static void bfs() {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> q = new ArrayDeque<>();
        
        // 1. 장애물 설치하기
        for(int i = 0 ; i < chk.length ; i++) {
            if(chk[i]) {
                int x = xList.get(i)[0];
                int y = xList.get(i)[1];
                map[x][y] = 'O';
            }
        }
        
        // 2. 선생님 위치들 큐에 추가 & 방문 표시
        for(int[] t : tList) {
            q.add(new int[] {t[0], t[1]});
            visited[t[0]][t[1]] = true;
        }
        
        // 3. 선생님 위치들에서 탐색 시작
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                // 💥 해당 방향으로 격자 끝까지 뻗어나가며 탐색
                while(nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    if(map[nx][ny] == 'O')  break;  // 장애물 있으면 종료
                    
                    visited[nx][ny] = true;
                    
                    // 💥 현재 이동 방향으로 한 칸 더 뻗어나가기
                    nx += dx[d];
                    ny += dy[d];
                }
            }
        }
        
        // 4. 모든 학생들이 감시를 피할 수 있다면, YES 출력
        boolean isOK = true;    // 모든 학생들이 감시 피했는지 나타내는 변수
        for(int[] s : sList) {
            if(visited[s[0]][s[1]]) {
                isOK = false;
            }
        }
        
        if(isOK) {  // 모든 학생들이 감시를 피했다면, YES 출력하고 종료
            System.out.println("YES");
            System.exit(0);
        }
        
        // 5. 장애물 있던 자리 원상복구
        for(int i = 0 ; i < chk.length ; i++) {
            if(chk[i]) {
                int x = xList.get(i)[0];
                int y = xList.get(i)[1];
                map[x][y] = 'X';
            }
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

1. 완전탐색을 많이 활용한 풀이!

장애물 배치할 때도 완전탐색을 사용하셨다.

[백준 18428] - 감시 피하기(JAVA)

static void dfs(int wall) {
    if (wall == 3) {
        bfs();
        return;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 'X') {
                map[i][j] = 'O';	// 장애물 설치
                dfs(wall + 1);
                map[i][j] = 'X';	// 원상복구
            }
        }
    }
}

 

 

2. 조금 더 짧은 풀이! ✅

[BJ] 18428 감시 피하기 Java

---

💦 어려웠던 점

- 4방향 탐색할 때 이 방향으로 어떻게 끝까지 전진하지?의 문제

 

 

🧐 새로 알게 된 내용

- 4방향 탐색할 때 한 방향에서 쭉 직진하는 방법 (while문을 사용하자!)

while(!q.isEmpty()) {
    int[] now = q.poll();

    for(int d = 0 ; d < 4 ; d++) {
        int nx = now[0] + dx[d];
        int ny = now[1] + dy[d];

        // 해당 방향으로 격자 끝까지 탐색
        while(nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if(map[nx][ny] == 'O')  break;  // 장애물 있으면 종료

            visited[nx][ny] = true;

            // 현재 이동 방향으로 이동 +1
            nx += dx[d];
            ny += dy[d];
        }
    }
}

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준 18428] - 감시 피하기(JAVA)