[Algorithm] SW 기출문제 - 연구소(14502) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 - 연구소 자바 풀이를 진행하도록 하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

1. 풀이 소스 :

 

import java.util.*;
import java.io.*;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Lab lab = new Lab(n, m);
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++)
                lab.setMap(row, col, parseInt(st.nextToken()));
        }
        
        lab.buildWall();
        System.out.println(lab.getSafeRegion());
    }
}

class Lab {
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};    
    
    int n; // row의 총 개수
    int m; // col의 총개수
    int minVirusCnt = Integer.MAX_VALUE; // 최소 바이러스 확진
    int virusCnt; // dfs로 실행된 각 조합에 바이러스 확진
    int[][] map; // 맵
    int wallsCnt = 3; // 벽의 개수 (무조건 3개를 세울 수 있으므로 초기화 3)
    
    boolean[][] visited; // 방문 여부
    List<Point> virus = new ArrayList<>(); // 바이러스 저장 리스트
    Combination combi; // 벽이 생성될 수 있는 조합
    
    Lab (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
        combi = new Combination();
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
        if (value == 0) combi.setInputs(new Point(row, col)); // 벽을 세울 수 있는 곳이라면 조합에 input 추가
        else if (value == 1) wallsCnt++; // 벽 개수 추가
        else virus.add(new Point(row, col)); // 바이러스 point 추가
    }
    
    void buildWall() {
        List<List<Point>> possibleCombi = combi.getCombination(); // 벽을 세울 수 있는 조합 생성
        
        for (List<Point> combis : possibleCombi) {
            for (Point point : combis) { // 각 조합에 있는 3가지 벽의 위치 하나씩
                map[point.row][point.col] = 1; // 벽 세우기
            }
            
            virusCnt = 0; // 각 조합 당 몇 개의 바이러스가 확진 되는지
            for (Point v : virus) {
                dfs(v.row, v.col); // dfs
            }
            
            minVirusCnt = Math.min(minVirusCnt, virusCnt); // 최소 바이러스 설정

            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++)
                    visited[row][col] = false; // 방문여부 다시 초기화
            }
            
            for (Point point : combis) {
                map[point.row][point.col] = 0; // 다시 벽 해제
            }
        }
    }
    
    void dfs(int row, int col) {
        
        visited[row][col] = true; // 방문 설정
        virusCnt++; // 바이러스 개수 증가
        
        for (int i = 0; i < 4; i++) {
            int nextR = row + DR[i]; // 다음 행
            int nextC = col + DC[i]; // 다음 열
            
            if (!isValid(nextR, nextC)) continue; // 이미 방문 혹은 인덱스 벗어났거나, 확진 가능한 곳이 아니라면
            dfs(nextR, nextC); // dfs
        }
    }
    
    int getSafeRegion() {
        return (n * m) - wallsCnt - minVirusCnt; // 총 안전 지대 = 총 장소 - 벽 - 확진자
    }
    
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m && !visited[row][col] &&
            map[row][col] == 0; // 유효한 인덱스 && 방문 X && 감염 안된 사람들
    }
    
    static class Point {
        int row;
        int col;
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    static class Combination { // 조합 생성
        List<Point> inputs = new ArrayList<>(); // 조합에 사용될 인풋
        List<List<Point>> combi = new ArrayList<>(); // 최종 조합

        Combination () {}

        void setInputs(Point point) {
            inputs.add(point); // 리스트에 추가
        }

        List<List<Point>> getCombination() {
            getCombinationHelper(3, 0, new ArrayList<>()); // 조합 재귀 실행
            return combi;
        }

        void getCombinationHelper(int k, int start, List<Point> current) {
            if (k == 0) {
                combi.add(new ArrayList<>(current)); // 깊은 복사로 combi에 추가
                return;
            }
            
            for (int i = start; i < inputs.size(); i++) {
                current.add(inputs.get(i)); // input에 있는 값 조합에 추가
                getCombinationHelper(k - 1, i + 1, current); // 가능한 개수 줄이고, 다음 번 조합은 i를 증가 시켜서 실행
                current.remove(current.size() - 1); // [1, 2]이 조합에 있는 경우 다음 조합에 영향을 주지 않기 위해 [1]로 설정하여 다음 조합 실행
            }
        }
    }
}

 

 

2. 풀이 중점 사항

 

해당 문제는 안전 지대를 최대한 늘릴 수 있는 벽 3개를 짓고, 최대 안전지대 개수를 출력하는 문제입니다.

따라서, 벽을 지을 수 있는 곳 3가지의 조합을 생성한 후, 하나씩 dfs를 진행하여 최대 안전지대 개수를 구하는 방법으로 진행하였습니다.

 

조합

 

조합은 재귀로 생성할 수 있습니다. 3가지의 벽을 세워야 하는데, 이미 벽이 있거나 확진자가 존재하는 곳이 있기 때문에,
벽을 지을 수 있는 Point를 인풋으로 설정하여 List에 넣은 후, 각 리스트에 있는 원소를 재귀로 탐색하여 3가지의 배열을 설정하는 Combination 클래스를 static으로 선언하였습니다.

 

 

static class Combination { // 조합 생성 
    List<Point> inputs = new ArrayList<>(); // 조합에 사용될 인풋 
    List<List<Point>> combi = new ArrayList<>(); // 최종 조합 

    Combination () {}

    void setInputs(Point point) {
        inputs.add(point); // 리스트에 추가 
    }

    List<List<Point>> getCombination() {
        getCombinationHelper(3, 0, new ArrayList<>()); // 조합 재귀 실행 
        return combi;
    }

    void getCombinationHelper(int k, int start, List<Point> current) {
        if (k == 0) {
            combi.add(new ArrayList<>(current)); // 깊은 복사로 combi에 추가 
            return;
        }

        for (int i = start; i < inputs.size(); i++) {
            current.add(inputs.get(i)); // input에 있는 값 조합에 추가 
            getCombinationHelper(k - 1, i + 1, current); // 가능한 개수 줄이고, 다음 번 조합은 i를 증가 시켜서 실행 
            current.remove(current.size() - 1); // [1, 2]이 조합에 있는 경우 다음 조합에 영향을 주지 않기 위해 [1]로 설정하여 다음 조합 실행 
        }
    }
}

 

중점 사항은, 이전 블록 퍼즐 문제와 비슷한 방법으로 재귀로 하나의 원소를 더한 후, 재귀 이후 다시 원소를 하나 제거해야 하는 것입니다.

이 코드는 다음의 순서로 진행됩니다.

 

[1, 2] -> [1, 2, 3] , [1, 2, 4](return) ...... -> getCombinationHelper() 종료 -> current.remove(current.size() - 1)

==> [1] 

 

다음 i++로 인해 inputs.get(i) = 3

[1, 3]

 

따라서, 각 원소에 대한 모든 조합을 구할 수 있습니다.

 

DFS 빌드 업

 

void buildWall() {
    List<List<Point>> possibleCombi = combi.getCombination(); // 벽을 세울 수 있는 조합 생성

    for (List<Point> combis : possibleCombi) {
        for (Point point : combis) { // 각 조합에 있는 3가지 벽의 위치 하나씩 
            map[point.row][point.col] = 1; // 벽 세우기
        }

        virusCnt = 0; // 각 조합 당 몇 개의 바이러스가 확진 되는지 
        for (Point v : virus) {
            dfs(v.row, v.col); // dfs
        }

        minVirusCnt = Math.min(minVirusCnt, virusCnt); // 최소 바이러스 설정 

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++)
                visited[row][col] = false; // 방문여부 다시 초기화 
        }

        for (Point point : combis) {
            map[point.row][point.col] = 0; // 다시 벽 해제
        }
    }
}

 

각 DFS 결과는 독립적으로 실행되어야 합니다. 예를 들어, 3가지의 조합 결과가 다음 3가지의 조합 결과에 영향을 주면 안 됩니다. 따라서, 모든 방문을 끝낸 이후, 최소 바이러스 확진 수를 구한 후, 방문 처리를 초기화하였습니다.

그리고 다시 벽을 해제하여, 다음 벽이 세워질 때 영향을 주지 않도록 하였습니다.

 

DFS

 

void dfs(int row, int col) {

    visited[row][col] = true; // 방문 설정 
    virusCnt++; // 바이러스 개수 증가 

    for (int i = 0; i < 4; i++) {
        int nextR = row + DR[i]; // 다음 행 
        int nextC = col + DC[i]; // 다음 열 

        if (!isValid(nextR, nextC)) continue; // 이미 방문 혹은 인덱스 벗어났거나, 확진 가능한 곳이 아니라면 
        dfs(nextR, nextC); // dfs 
    }
}

virusCnt는 인스턴스 변수로 설정되어 있기 때문에 각 dfs가 진행되더라도 전역적으로 공유하여 사용될 수 있습니다.

유효한 범위이고 방문하지 않았으며 확진 가능한 곳 (map[r][c] = 0)인 곳만 다음 dfs로 탐색을 진행할 수 있습니다.

나머지 자세한 부분은 주석화 하였습니다. 

 

이상으로 SW 기출문제 연구소 풀이를 마치도록 하겠습니다. 감사합니다.