[BackTracking] 백준 18428번 감시 피하기 - JAVA
오늘은 23.11.23에 풀었던 알고리즘 스터디의 첫 번째 문제!
지연이가 요청했던 그 문제!!!
감시피하기 문제를 다시 보고 리뷰하는 시간을 갖도록 하겠다.
다시 보니까 꽤 난이도 있는 문제여~
1. 출처
https://www.acmicpc.net/problem/18428
18428번: 감시 피하기
NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복
www.acmicpc.net
- N*N 복도에 학생과 선생님의 위치가 주어짐
- 3개의 장애물을 설치해서 학생들을 선생님 감시 하에서 피하게 해야함
- 선생님은 자신의 4방을 거리 제한없이 감시할 수 있음
- 단, 선생님은 장애물 뒤까지는 볼 수 없음
- 감시를 피할 수 있으면 "YES", 없으면 "NO"
2. 설계
1. 어떤 기법을 쓸 것이냐?
우리는 복도 좌표 중 장애물 위치 3곳을 선정할 것이다.
그런데 장애물 3곳의 위치가 아래처럼 장애물 순서가 다르게 뽑혔다고 해도 같은 상황으로 간주하기 때문에
백트래킹 기법 중 Combination 기법을 사용할 것이다.
백트래킹 기법 사용 상황 참고
부분집합 / 조합 / 순열 / NEXT PERMUTATION 총정리
1. 부분집합 - power set 공집합일 때 부터 1,2,3의 조합이 모두 들어갈 때 까지 즉, 집합이 0개일 때부터 1개일 때 2개일 때... 전체 다 들어갔을 때를 따져 준다. package arr; import java.util.Scanner; /** * 부분
tksgk2598.tistory.com
- 순서가 중요하다(다른 상황으로 본다) : Permutation
- 순서가 중요하지 않다(같은 상황으로 본다) : Combination
2. 자세한 설계 설명
1) 선생님과 빈공간 위치를 리스트에 저장한다.
빈공간 리스트를 만드는 이유 : 장애물 3곳을 Combination을 이용해 선정하기 위함
선생님 리스트를 만드는 이유 : 무제한 4방 탐색을 통해 걸리는 학생이 있는지 파악하기 위함
즉, 학생의 위치는 리스트로 따로 저장할 필요가 없다. (복도좌표 map에만 저장하면 됨)
//1. X위치 저장, 선생님 위치 저장
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
map[i][j] = sc.next().charAt(0);
//빈공간 위치
if(map[i][j] == 'X'){
xList.add(new Node(i, j));
}
//선생님 위치 저장
else if(map[i][j] == 'T'){
teacherList.add(new Node(i, j));
}
}
}
2) 빈공간 리스트를 이용해 장애물을 설치할 3곳을 Combination으로 선정
public static void Combination(int depth, int idx){
if(depth==3){
//3곳에 장애물을 설치했을 때 선생님의 감시를 모두 막을 수 있는지 체크
return;
}
if(idx==xList.size()) return; //모든 빈공간 조사했다는 의미
sel[depth]=xList.get(idx);
Combination(depth+1, idx+1);//선택
Combination(depth, idx+1);//미선택
}
위 코드는 기본 Combination 코드이다.
sel은 내가 만든 Node class(x,y 좌표가 들어감)의 배열이다.
빈공간 리스트(xList)를 순차적으로 탐색하며 이 빈공간을 선택할 경우와 미선택할 경우를 따져준다.
3곳을 모두 선택했을 경우 설치한 3곳의 장애물이 선생님의 감시를 모두 막을 수 있는지 체크하는 함수로 넘어간 다음 스레드를 끝내고,
빈공간을 모두 조사했다면 그냥 스레드를 끝낸다.
3) 3개 장애물이 잘 설치되었는지 체크하기 전
3개 장애물이 잘 설치되었는지 체크하는 함수로 넘어가기 전에
복도 좌표(map)을 copy해서 copy본에 장애물 3개를 설치하고, 함수로 넘겨줘야 한다.
왜냐하면 원본에 장애물을 설치하면, 다음 가정을 고려하기 위해 장애물을 빼주고, 넣어주고 하는 작업이 번거롭기 때문이다.
public static void Combination(int depth, int idx){
if(depth==3){ //3곳에 장애물을 설치했을 때 선생님의 감시를 모두 막을 수 있는지 체크
//새로운 copyMap 생성 -> 1차원만 가능
char[][] copyMap = new char[N][N];
for(int i=0;i<N;i++) copyMap[i] = map[i].clone();
//3개조합 copyMap에 'O'표시
for(int i=0;i<3;i++){
copyMap[sel[i].x][sel[i].y]='O';
}
if(Check(copyMap)){// 가능한 조합인가?
result = "YES";
}
return;
}
if(idx==xList.size()) return; //모든 빈공간 조사했다는 의미
sel[depth]=xList.get(idx);
Combination(depth+1, idx+1);//선택
Combination(depth, idx+1);//미선택
}
- clone은 1차원 배열 복사가 가능하다.
- map은 복도 좌표를 그려놓은 2차원 배열이기 때문에 for로 1row씩 복사한다.
- 위에서 말했듯이 sel은 내가 만든 Node class(x,y 좌표가 들어감)의 배열이다. 장애물로 선택한 좌표에 'O'를 표시해준다.
- 복사된 배열은 Check(선생님의 감시를 피할 수 있는가 여부 반환하는 함수)로 넘겨준다.
- Check에서 true가 넘어오면 전역 변수 result에 "YES"를 저장한다.
4) 선생님의 감시를 피할 수 있는가 여부를 반환하는 함수
선생님의 감시는 4방 탐색으로 이뤄지고, 거리에 제한이 없다.
선생님들의 위치 좌표 리스트(teacherList)에서 선생님 한 분씩 뽑아 4방을 while로 탐색한다.
- while로 한 방향을 쭉 탐색하며, 장애물을 만나면 다른 방향 탐색하게 while break을 해준다.
- 학생을 만나면 감시를 피하지 못한 경우이기 때문에 return false를 해주고, 해당 함수를 멈춘다.
//학생들은 선생님에게 모두 걸리지 않을 수 있을까?
public static boolean Check(char[][] copyMap){
for(int i=0;i<teacherList.size();i++){
Node curTeacher = teacherList.get(i);
//4방탐색
for(int d=0;d<4;d++){
int nextR = curTeacher.x;
int nextC = curTeacher.y;
while (true) {
nextR += drc[d][0];
nextC += drc[d][1];
//경계체크
if(nextR<0 || nextR>=N || nextC<0 || nextC>=N) break;
//장애물 체크
if(copyMap[nextR][nextC]=='O') break;
//학생체크
if(copyMap[nextR][nextC]=='S') return false;
}
}
}
return true;
}
해당 함수에서 true가 넘어가면 Combination 함수에서 전역변수 result="YES"로 셋팅할 것이다.
3. 전체 코드
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main { // 제한시간 2초
static int N;
static char[][] map;
static List<Node> xList = new ArrayList<>();//빈공간 모아둔 곳
static List<Node> teacherList = new ArrayList<>();//선생님들 좌표를 모아둔 곳
static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};//상하좌우
static Node[] sel = new Node[3];//장애물은 고정 3개
static String result = "NO";
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
//변수 선언
map = new char[N][N];
//1. X위치 저장, 선생님 위치 저장
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
map[i][j] = sc.next().charAt(0);
//빈공간 위치
if(map[i][j] == 'X'){
xList.add(new Node(i, j));
}
//선생님 위치 저장
else if(map[i][j] == 'T'){
teacherList.add(new Node(i, j));
}
}
}
//2. 빈공간 중 고정 3개 조합 꾸리기 -> Combination함수
Combination(0, 0);
System.out.println(result);
}
//3개 조합
public static void Combination(int depth, int idx){
if(depth==3){
//새로운 copyMap 생성 -> 1차원만 가능
char[][] copyMap = new char[N][N];
for(int i=0;i<N;i++) copyMap[i] = map[i].clone();
//3개조합 copyMap에 'O'표시
for(int i=0;i<3;i++){
copyMap[sel[i].x][sel[i].y]='O';
}
if(Check(copyMap)){// 가능한 조합인가?
result = "YES";
}
return;
}
if(idx==xList.size()) return;
sel[depth]=xList.get(idx);
Combination(depth+1, idx+1);//선택
Combination(depth, idx+1);//미선택
}
//학생들은 선생님에게 모두 걸리지 않을 수 있을까?
public static boolean Check(char[][] copyMap){
for(int i=0;i<teacherList.size();i++){
Node curTeacher = teacherList.get(i);
//4방탐색
for(int d=0;d<4;d++){
int nextR = curTeacher.x;
int nextC = curTeacher.y;
while (true) {
nextR += drc[d][0];
nextC += drc[d][1];
//경계체크
if(nextR<0 || nextR>=N || nextC<0 || nextC>=N) break;
//장애물 체크
if(copyMap[nextR][nextC]=='O') break;
//학생체크
if(copyMap[nextR][nextC]=='S') return false;
// copyMap[nextR][nextC] = 'w'; //잘 탐색했나 확인용
}
}
}
return true;
}
static public class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
스터디 시작한지 벌써 3달이라니.. 감회가 새롭네...