2문제 모두 DFS 알고리즘 문제로 푸는 방식이 비슷하여 가져와봤다.
연구소
https://www.acmicpc.net/problem/14502
package DFS_BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class practice {
public static int[] dx={0,1,0,-1};
public static int[] dy={1,0,-1,0};
public static int result=0;
public static int[][] temp;
public static int[][] map;
public static int N,M;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
map=new int[N][M];
temp=new int[N][M];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<M;j++){
map[i][j]=Integer.parseInt(st.nextToken());
}
}
DFS(0);
System.out.println(result);
}
public static void DFS(int count){
if(count==3){
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
temp[i][j]=map[i][j];
}
}
for(int i=0;i<N;i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 2) {
virus(i,j);
}
}
}
result=Math.max(result,getScore(temp));
return;
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(map[i][j]==0){
map[i][j]=1;
DFS(count+1);
map[i][j]=0;
}
}
}
}
public static void virus(int i,int j){
for (int k = 0; k < 4; k++) {
int nx =i+dx[k];
int ny=j+dy[k];
if(nx<0||ny<0||nx>=N||ny>=M){
continue;
}
if(temp[nx][ny]==0){
temp[nx][ny]=2;
virus(nx,ny);
}
}
}
public static int getScore(int[][] map){
int score=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++) {
if(map[i][j]==0){
score++;
}
}
}
return score;
}
}
- 벽 3개 세우기
- 벽 완료하면 바이러스 퍼지게 실험
- 바이러스 실험 완료하면 점수 도출해서 최대값 찾기
1. 벽 3개 랜덤하게 세우기
알고리즘에서 랜덤하게 나오면 -> 대부분 완전탐색 문제이다. 완전 탐색 문제라면 DFS/BFS를 꼭 고려해보자.
이 문제는 DFS를 활용하여 풀었다. DFS와 BFS 중 뭐로 풀어야할지 고민될때가 있다. 사실 두개 다 사용 가능한 경우도 많다. 이 문제는 벽을 하나 고정하고 깊게 여러 경우를 살펴보니 DFS를 사용하였다.
public static void DFS(int count){
if(count==3){//벽 3개 다 새웠으면
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
temp[i][j]=map[i][j];
}
}//해당 map을 temp임시 2차원 배열로 옮김 -> 여러번 실험해야하니깐 map은 온전하게 초기 상태를 유지해야함
for(int i=0;i<N;i++) {//바이러스 발견하면 퍼뜨림
for (int j = 0; j < M; j++) {
if (map[i][j] == 2) {
virus(i,j);//바이러스 전염 과정도 DFS이다.
}
}
}
//최댓값 선정
result=Math.max(result,getScore(temp));
return;
}
//벽 세우는 코드
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
//해당 map에 아무것도 없음 벽세우기
if(map[i][j]==0){
map[i][j]=1;
DFS(count+1);//벽 개수+1
map[i][j]=0;//재귀적으로 벽 세운거 없애줌 개수의 경우 매개변수로 count+1를 해줬기 때문에 return을 통해 돌아오면 자동으로 count-1이 됨
}
}
}
}2. 바이러스 실험
public static void virus(int i,int j){
//상하좌우로 바이러스 실험
for (int k = 0; k < 4; k++) {
int nx =i+dx[k];
int ny=j+dy[k];
//map 범위 넘어가는 경우
if(nx<0||ny<0||nx>=N||ny>=M){
continue;
}
//벽 없으면 바이러스 퍼짐
if(temp[nx][ny]==0){
temp[nx][ny]=2;
virus(nx,ny);
}
}
}3. 점수 구하기
public static int getScore(int[][] map){
int score=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++) {
//바이러스 퍼진 곳 없으면 점수 + 1
if(map[i][j]==0){
score++;
}
}
}
return score;
}감시 피하기
https://www.acmicpc.net/problem/18428
package DFS_BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class practice {
public static int[] dx={0,-1,0,1};
public static int[] dy={1,0,-1,0};
public static int N=0;
public static boolean check=false;
public static int[][] map;
public static ArrayList<Integer> teacherX=new ArrayList<>();
public static ArrayList<Integer> teacherY=new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map=new int[N][N];
StringTokenizer st=null;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
String s=st.nextToken();
if(s.equals("S")){
map[i][j]=1;
}else if(s.equals("T")){
map[i][j]=2;
teacherX.add(i);teacherY.add(j);
}else{
map[i][j]=0;
}
}
}
DFS(0);
if(check)
System.out.println("YES");
else
System.out.println("NO");
}
public static void DFS(int count){
if(count==3){
if(!teacherSearchStudent()){
check=true;}
return;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(map[i][j]==0) {
map[i][j] = 3;
DFS(count + 1);
map[i][j] = 0;
}
}
}
}
public static boolean teacherSearchStudent(){
for(int i=0;i<teacherX.size();i++){
int x=teacherX.get(i);
int y=teacherY.get(i);
for(int j=x-1;j>=0;j--){
if(map[j][y]==1) {return true;}
if(map[j][y]==3) {break;}
}
for(int j=x+1;j<N;j++){
if(map[j][y]==1) {return true;}
if(map[j][y]==3) {break;}
}
for(int j=y-1;j>=0;j--){
if(map[x][j]==1) {return true;}
if(map[x][j]==3) {break;}
}
for(int j=y+1;j<N;j++){
if(map[x][j]==1) {return true;}
if(map[x][j]==3) {break;}
}
}
return false;
}
}
위 연구소와 비슷하게 벽을 세워 선생님의 감시를 피해야한다.
1. 벽 3개 세우기
2. 선생님 감시 확인하기
1. 벽 3개 세우기
public static void DFS(int count){
//벽 3개면 선생님 감시 시작
if(count==3){
if(!teacherSearchStudent()){
check=true;}
return;
}
//벽 랜덤하게 세우기
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(map[i][j]==0) {
map[i][j] = 3;
DFS(count + 1);
map[i][j] = 0;
}
}
}
}2. 선생님 감시 피하기
연구소 문제의 경우 바이러스 감염이 벽을 만나 불가능 하더라도 전체적으로 모든 바이러스의 과정을 끝내야한다.
선생님 감시 피하기의 경우 한 학생만 걸려도 끝나고 벽을 만나면 더 이상 감시를 못하기 때문에 상하좌우를 반복문을 통해 살펴보기보단 따로 나눠서 코드를 작성했다.
public static boolean teacherSearchStudent(){
for(int i=0;i<teacherX.size();i++){
int x=teacherX.get(i);
int y=teacherY.get(i);
//왼쪽
for(int j=x-1;j>=0;j--){
if(map[j][y]==1) {return true;}
if(map[j][y]==3) {break;}
}
//오른쪽
for(int j=x+1;j<N;j++){
if(map[j][y]==1) {return true;}
if(map[j][y]==3) {break;}
}
//위
for(int j=y-1;j>=0;j--){
if(map[x][j]==1) {return true;}
if(map[x][j]==3) {break;}
}
//아래
for(int j=y+1;j<N;j++){
if(map[x][j]==1) {return true;}
if(map[x][j]==3) {break;}
}
}
return false;
}