[백준] 18428 감시 피하기(조합+BFS_Java)
드디어
드디어 푼 문제!
문제 설명을 올려준
산하언니께 무한한 영광을 드립니다.
사실 검색하고 찾아봐도,
왜 조합을 저렇게 하지?
저렇게 하면 완전탐색이 안되지 않나?
하면서 계속 궁금했는데,
산코중 덕분에 다른 방법을 찾았네융
시작-!
문제
https://www.acmicpc.net/problem/18428
18428번: 감시 피하기
NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복
www.acmicpc.net
설계
알고리즘 설계[접근방법] : 조합 + BFS
가장 먼저, 빈 공간인 X들 사이에서 3개를 골라야 한다.
| S | X | X | T |
| X | X | X | X |
| X | S | T | X |
만약 이 그래프에서 노란색 배경의 X 자리에 장애물을 설치한다고 가정해보자.
3개의 X좌표 중 어느 곳에 먼저 장애물을 설치해도 선생님한테 들키는 건 똑같다. 장애물을 설치하는 좌표가 같다면, 순서는 다르다고 해도 선생님이 탐색하는 것에 다른 점이 없기 때문에 조합으로 풀이가 가능하다.
여기서 조합과 순열의 차이는 순서가 바뀌는 것이 의미가 있을 때 순열로 푸는 것이고,
순서가 바뀌어도 의미가 없다면 조합으로 풀이가 가능하다.
그 후, 조합으로 장애물을 설치할 좌표를 선택했다면, BFS로 선생님의 감시를 피할 수 있는지 확인해야 한다.
4방향으로 배열을 끝까지 탐색해서 학생을 발견하지 못한다면, 장애물 설치를 잘한 것이다.
풀이과정
1.
좌표와 관련된 풀이가 많아서, 좌표 정보를 담는 class Node를 생성했다.
Node에는 x, y로 구성되어 있고, 생성자와 toString을 만들어줬다.
2.
가장 먼저, n을 입력받는다.
n의 크기만큼 String 2차원 배열 map을 생성 후 좌표 값을 입력받는다.
3.
4방향 탐색에 필요한 배열 r, c를 만들고,
선생님과 빈공간 좌표를 담을 xList와 tList를 생성한다.
4.
map을 탐색하면서 현재 좌표가 x라면 xList에 저장하고, T라면 tList에 저장한다.
5.
장애물을 놓을 좌표를 담을 sel를 생성한다.
6.
DFS에 들어와서 조합을 시작한다.
depth은 현재 장애물 설치한 개수를 의미하고, idx는 xList에서 어느 좌표를 sel에 넣을지를 담당할 인덱스다.
idx가 xList의 마지막까지 탐색했다면, X좌표는 모두 탐색한 것이므로 DFS 메서드는 종료된다. 만약 depth가 3이라면 장애물 설치에 필요한 좌표를 모두 고른 것이므로, 이제 선생님 감시에 피할 수 있을지 확인하면 된다.
현재 idx가 가리키는 X좌표를 선택하기 위해 sel[depth] = xList.get(idx);를 실행한다.
그 후, 다음 자리를 선택하기 위해 DFS(depth+1, idx+1); 를 실행한다.
현재 idx가 가리키는 X좌표를 선택하지 않았을 경우도 위해 DFS(depth, idx+1); 를 실행한다.
항상 배열만 풀어보다가, 리스트로 푸는 건 처음인데 배열에서 리스트로만 변경되고 나머지 코드는 똑같다.
7.
장애물을 설치할 좌표 3개를 모두 선택했다면, 선생님의 감시를 피할 수 있는지 확인하면 된다.
장애물 설치 좌표는 매번 바뀌기 때문에 map 배열에 하는 것은 옳지 않고, map배열을 복사해야 한다.
map 배열을 복사 후, 장애물을 설치할 좌표 값을 O으로 변경한다.
8.
tList에 있는 선생님의 좌표에서 4방향 탐색을 진행하면서 학생인 S가 있는지 확인한다.
만약, 탐색하고 있는 좌표가 배열 밖을 벗어났다면 탐색을 종료한다.
또한 탐색하고 있는 좌표의 값이 O으로 장애물이라면 탐색을 종료한다.
탐색하고 있는 좌표가 S라면, 학생이므로 탐색을 종료하고 false를 반환한다.
만약 모든 선생님의 좌표에서 탐색했을 때, S를 찾지 못했다면 장애물을 잘 설치한 것이므로 true를 반환한다.
9.
DFS메서드로 들어와서, BFS메서드의 반환값이 true라면 result값을 YES로 변경한다.
10.
모든 메서드가 종료된 후에 result를 출력한다.
코드
import java.util.*;
public class Test_184828_감시피하기 {
static String[][] map;
static int[] r, c;
static int n;
static String result;
static List<Node> xList, tList;
static Node[] sel;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
//입력받기
map = new String[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
map[i][j] = sc.next();
}
}
//사방향 탐색 배열
r = new int[] {-1, 0, 1, 0};
c = new int[] {0, 1, 0, -1};
//빈공간, 선생님 좌표 list에 저장
xList = new ArrayList();
tList = new ArrayList();
for(int i=0; i<map.length; i++) {
for(int j=0; j<map.length; j++) {
if(map[i][j].equals("T")) tList.add(new Node(i, j));
else if(map[i][j].equals("X")) xList.add(new Node(i, j));
}
}
//장애물을 놓을 좌표 배열
sel = new Node[3];
//DFS 실행
result = "NO";
DFS(0, 0);
//출력
System.out.println(result);
}
//완전 탐색
public static void DFS(int depth, int idx) {
if(depth==3) {
if(BFS()) result = "YES";
return;
}
if(idx==xList.size()) return;
sel[depth] = xList.get(idx);
DFS(depth+1, idx+1); //현재 자리를 선택하고, 다음 자리를 탐색한다.
DFS(depth, idx+1); //현재 자리를 선택하지 않고, 다음 자리를 탐색한다.
}
//BFS
public static boolean BFS() {
//map 배열 복사
String[][] copy = new String[n][n];
for(int i=0; i<map.length; i++) {
copy[i] = map[i].clone();
}
//장애물 설치
for(int i=0; i<sel.length; i++) {
Node node = sel[i];
copy[node.x][node.y] = "O";
}
//선생님 탐색
for(int i=0; i<tList.size(); i++) {
Node node = tList.get(i);
for(int k=0; k<4; k++) {
int dr = node.x;
int dc = node.y;
while(true) {
dr +=r[k];
dc +=c[k];
if(!(0<=dr && dr<n && 0<=dc && dc<n)) break;
if(copy[dr][dc].equals("O")) break;
if(copy[dr][dc].equals("S")) return false;
}
}
}
return true;
}
}
//좌표 class
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "Node [x=" + x + ", y=" + y + "]";
}
}
(❁´◡`❁)
끝!