[Algorithm] 감시 피하기

풀이

먼저, 벽이 3개인 경우를 찾아 선생님 위치에서 상하좌우를 확인하도록 생각했다.

 

1. 벽 설치

벽이 3개가 아닌 경우 벽을 설치하도록 dfs로 구현했다.

벽이 3개가 될 경우 그래프를 탐색하면서 선생님이 위치한 좌표를 찾아 체크한다.

선생님 수 만큼 체크가 되어야 한다. (모든 선생님이 학생을 못 봐야 함.)

여기서 선생님 한명만 안보여도 통과하게 로직을 짜서 문제가 되었다.

	public static void dfs(int cnt) {
        if (cnt == 3) {
            // 벽이 3개가 설치된 경우
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 'T') {
                        // 선생님 위치에서 학생들이 보이는지 check
                        if (check(i, j)) count++;
                    }
                }
            }
            if (count == teachers) result = true;
        } else {
            // 장애물 3개가 아니면 장애물 설치
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 'X') {
                        cnt++;
                        graph[i][j] = 'O';
                        dfs(cnt);
                        cnt--;
                        graph[i][j] = 'X';
                    }
                }
            }
        }
    }

2. 장애물 3개가 되면 선생님의 시야 체크

선생님의 시야 체크는 선생님 위치에서 상, 하, 좌, 우를 탐색하도록 구현했다.

학생을 만나면 false를 반환하며, 중간에 벽을 만나면 탐색을 그만둔다.

모든 방향에서 학생을 만나지 않으면 true를 반환하고 마친다.

    public static boolean check (int x, int y) {
        // 선생님 상하좌우 시야에 학생이 걸리는지
        // 안걸리면 true, 걸리면 false
        boolean isHidden = true;
        // 가다가 벽 만나면 break, 학생 만나면 false
        // 현재 위치에서 위로
        for (int i = x; i >= 0; i--) {
            if (graph[i][y] == 'S') isHidden = false;
            if (graph[i][y] == 'X') break; 
        }
        // 아래로
        for (int i = x; i < n; i++) {
            if (graph[i][y] == 'S') isHidden = false;
            if (graph[i][y] == 'X') break; 
        }
        // 왼쪽
        for (int i = y; i >= 0; i--) {
            if (graph[x][i] == 'S') isHidden = false;
            if (graph[x][i] == 'X') break; 
        }
        // 오른쪽
        for (int i = y; i < n; i++) {
            if (graph[x][i] == 'S') isHidden = false;
            if (graph[x][i] == 'X') break; 
        }
        return isHidden;
    }

전체 소스코드

import java.util.*;

class Main {

    public static int n;
    public static char[][] graph = new char[6][6];
    public static int teachers = 0;
    public static boolean result = false; // 만약 한번이라도 안보이면 숫자 카운트

    public static void dfs(int cnt) {
        if (cnt == 3) {
            // 벽이 3개가 설치된 경우
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 'T') {
                        // 선생님 위치에서 학생들이 보이는지 check
                        if (check(i, j)) count++;
                    }
                }
            }
            if (count == teachers) result = true;
        } else {
            // 장애물 3개가 아니면 장애물 설치
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 'X') {
                        cnt++;
                        graph[i][j] = 'O';
                        dfs(cnt);
                        cnt--;
                        graph[i][j] = 'X';
                    }
                }
            }
        }
    }

    public static boolean check (int x, int y) {
        // 선생님 상하좌우 시야에 학생이 걸리는지
        // 안걸리면 true, 걸리면 false
        boolean isHidden = true;
        // 가다가 벽 만나면 break, 학생 만나면 false
        // 현재 위치에서 위로
        for (int i = x; i >= 0; i--) {
            if (graph[i][y] == 'S') isHidden = false;
            if (graph[i][y] == 'X') break; 
        }
        // 아래로
        for (int i = x; i < n; i++) {
            if (graph[i][y] == 'S') isHidden = false;
            if (graph[i][y] == 'X') break; 
        }
        // 왼쪽
        for (int i = y; i >= 0; i--) {
            if (graph[x][i] == 'S') isHidden = false;
            if (graph[x][i] == 'X') break; 
        }
        // 오른쪽
        for (int i = y; i < n; i++) {
            if (graph[x][i] == 'S') isHidden = false;
            if (graph[x][i] == 'X') break; 
        }
        return isHidden;
    }

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.next().charAt(0);
                if (graph[i][j] == 'T') teachers++;
            }
        }
        sc.close();

        dfs(0);

        System.out.println((result) ? "YES" : "NO");
        
        
    }
    
}

 

풀면서 벽을 세우는 경우의 수가 조합이랑 비슷하지 않나 생각했다.

깃헙에 풀이는 조합을 이용해 풀었다. 벽의 위치를 조합으로 정할 수 있다.

나중에 깃헙의 코드도 분석해봐야겠다.

 

이번 문제는 먼저 요구사항을 정리하면서 풀이했다.

무작정 코드부터 작성하는 것이 아니라 요구사항을 정리하고, 기능별로 구현하기 위해 고민했다.

훨씬 편하게 풀 수 있었다. (중간에 막혀도 어느 부분에서 문제가 생긴지 쉽게 찾게됨)