📌 문제 설명
N x N크기의 복도에서T(선생님),S(학생),X(빈칸)이 배치되어 있다.- 선생님은 상, 하, 좌, 우 방향으로 감시를 할 수 있으며, 장애물
O가 있으면 감시를 막을 수 있다. - 장애물 3개를 설치하여 학생이 감시를 피할 수 있는 경우 "YES", 불가능하면 "NO"를 출력하는 문제.
💡 접근 방식
🔹 1️⃣ 3개의 장애물 설치 (완전탐색)
- 빈칸(
X) 중에서 3개의 장애물을 선택하는 모든 경우를 시도해야 한다. N x N크기이므로,X의 개수가 많지 않다면 3중 반복문으로 해결 가능.- 장애물이 많아지면 백트래킹을 활용한 DFS로 해결 가능.
🔹 2️⃣ 장애물을 배치한 후 감시 시뮬레이션
- 모든 선생님(T)의 위치에서 상, 하, 좌, 우 방향으로 감시를 수행.
- 감시 도중 학생(S)을 발견하면 실패, 장애물(O)이나 벽에 막히면 탐색 종료.
🔹 3️⃣ 가능한 경우 찾기
- 모든 선생님이 학생을 감시할 수 없는 경우
"YES"출력. - 모든 장애물 배치 경우를 시도해도 실패하면
"NO"출력.
📝 코드 구현
import java.io.*;
import java.util.*;
public class Main {
/*
* 특정 장애물을 미리 설치해두고 선생님의 좌표를 돌아가면서
* 선생님이 학생을 한 명이라도 발견할 수 있을지를 판단해서 해결
* 특정 장애물을 설치하는 것은 3중 반복문으로 해결,
* 만약 장애물의 개수가 많아진다면 백트래킹으로 해결 가능
* 선생님의 좌표에서 4가지 방향으로 특정 장애물, 선생님, 학생을 만날 때까지 반복해서 이동
* 선생님들 중 한 명이라도 학생을 발견하면 실패이므로 AND 연산 사용
*/
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N;
private static char[][] map;
private static List<int[]> teacherPoints = new ArrayList<>();
public static void main(String[] args) throws IOException {
setting();
System.out.println(findAnswer() ? "YES" : "NO");
}
private static boolean findAnswer() {
for (int j1 = 0; j1 < N * N; j1++) {
if (map[j1 / N][j1 % N] == 'X') {
map[j1 / N][j1 % N] = 'O';
for (int j2 = j1 + 1; j2 < N * N; j2++) {
if (map[j2 / N][j2 % N] == 'X') {
map[j2 / N][j2 % N] = 'O';
for (int j3 = j2 + 1; j3 < N * N; j3++) {
if (map[j3 / N][j3 % N] == 'X') {
map[j3 / N][j3 % N] = 'O';
boolean isAnswerFind = true;
for (int[] teacher : teacherPoints) {
isAnswerFind &= !findStudent(teacher[0], teacher[1]);
}
if (isAnswerFind) return true;
map[j3 / N][j3 % N] = 'X';
}
}
map[j2 / N][j2 % N] = 'X';
}
}
map[j1 / N][j1 % N] = 'X';
}
}
return false;
}
private static boolean findStudent(int tx, int ty) {
int[] dix = {-1, 0, 1, 0};
int[] diy = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int dx = tx + dix[i];
int dy = ty + diy[i];
while (dx >= 0 && dx < N && dy >= 0 && dy < N) {
if (map[dx][dy] == 'O' || map[dx][dy] == 'T') break;
if (map[dx][dy] == 'S') return true;
dx += dix[i];
dy += diy[i];
}
}
return false;
}
private static void setting() throws IOException {
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] == 'T') teacherPoints.add(new int[]{i, j});
}
}
}
}🧐 코드 분석
| 함수 | 역할 |
|---|---|
setting() | N x N 복도를 입력받고, 선생님 위치 저장 |
findAnswer() | 3개의 장애물을 설치하는 모든 경우 탐색 |
findStudent(tx, ty) | 특정 선생님이 감시하는 학생이 있는지 검사 |
printMap() | (디버깅용) 현재 맵 상태 출력 |
🚀 시간복잡도 분석
- 장애물 3개 설치하는 모든 경우의 수:
- 최대
N^2개의 빈칸에서 3개를 선택 → O(N^6) N ≤ 6이므로 완전 탐색 가능!
- 최대
- 각 장애물 배치 후 감시 검사 (
findStudent)- 선생님 수
M에 대해 4방향 탐색 → O(MN)
- 선생님 수
- 최종 시간복잡도:
O(N^6 * M * N) ≈ O(6^6 * 5 * 6) ≈ O(46656)- 충분히 해결 가능!
🎯 결론
✅ 완전 탐색(브루트포스) + 시뮬레이션을 활용한 문제
✅ 백트래킹을 활용하면 N이 커져도 확장 가능
✅ N ≤ 6이므로 3중 반복문으로 해결 가능! 🚀
🔹 N이 커지면 백트래킹(DFS) 방식으로 최적화 가능!
private static boolean backtrack(int count, int start) {
if (count == 3) return findAnswer(); // 장애물 3개 배치 완료 시 체크
for (int i = start; i < N * N; i++) { // start부터 탐색하여 중복 방지
int x = i / N, y = i % N;
if (map[x][y] == 'X') {
map[x][y] = 'O'; // 장애물 배치
if (backtrack(count + 1, i + 1)) return true; // 다음 위치부터 탐색
map[x][y] = 'X'; // 원상 복구
}
}
return false;
}👉 findAnswer() 대신 backtrack(0)을 호출하면 재귀 방식으로 최적화 가능! 🚀
멋있는 사람 - 일단 하자