[JAVA / PYTHON] 연구소 3 (백준 17142) - 삼성기출

자바로 bfs,dfs 문제를 풀어본적이 없어서 간단한 bfs 문제를 풀어보려고 시도했다. 

 

이전에 삼성 sw 역량테스트를 준비하면서 파이썬으로 쉽게 풀었지만 이제는 자바에 익숙해 지고 싶어서 자바로 풀어보았다.

 

자바로 풀면서 놀랐던것은 왜 순열과 조합과 관련한 라이브러리가 없는 걸까... 물론 분명히 있을거 같은데 본인이 못찾는 것일 수도 있다.

 

귀찮지만 직접 조합을 구현했다. 조합은 dfs로 구현하였다.

 

문제를 푸는 알고리즘은 그림으로 표현하겠다.

 

 

 

 

 

위와 같은 연구소 배열이 있다고 하자. 값이 2인것은 바이러스가 놓일 수 있는 위치다. 바이러스가 놓인 위치가 아니다. 이 중에서 2개를 활성화 한다고 하면 활성화 한곳은 0 으로 바꾸고 visited 에서 해당위치에 1로 바꿔준다. 또한 비활성화한 곳은 -1로 둔다.

즉 문제풀이의 초기 상태는 아래와 같다.

빨간 별이 활성화된 상태이며 검은 별은 비활성화된 상태이다. 시간에 따라 어떻게 바뀌는 지 살펴보자.

 

이제 더이상 진행하지 않는다. 여기서 lab 배열중에visited 가 1이면서 가장 큰값인 4를 고르면 답이 되겠거니와 하겠지만

 

4는 이미 바이러스인 상태다. 비활성된 바이러스도 바이러스다. 따라서 추가적으로 조건을 거는데 기존의 배열에서 -1이 아니면서 빨간 별들중에 가장 큰값을 고르면 된다.  이는 답이 0이 되는것도 모두 커버할수 있다.

 

추가로 조합으로 바이러스를 선택하는 경우는 설명하지 않겠다. 다음에...

 

코드는 아래와 같다. 자바와 파이썬이다.

 

import sys
input = sys.stdin.readline

from itertools import combinations as comb
from collections import deque

n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
#바이러스 위치
v_idx=[]

dx = [0,0,-1,1]
dy = [1,-1,0,0]

# v_idx 중에서 *가 아닌 것들을 m개를 bfs 돌리자
def bfs_check():
    q = deque([])
    ch = [[0 for _ in range(n)] for _ in range(n)]
    for v in v_idx:
        if a[v[0]][v[1]]==2:
            q.append([v[0],v[1],0])
    tmp_ans = 0
    while q:
        x,y,cnt = q.popleft()

        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n and ch[nx][ny]==0 and (a[nx][ny]==0 or a[nx][ny]=='*'):
                ch[nx][ny]=1
                q.append([nx,ny,cnt+1])
                if a[nx][ny]==0:
                    tmp_ans=cnt+1

    for i in range(n):
        for j in range(n):
            if a[i][j]==0 and ch[i][j]==0:
                return 987654321
    return tmp_ans
for i in range(n):
    for j in range(n):
        if a[i][j]==2:
            v_idx.append([i,j])
ans = 987654321
for c in comb(v_idx,len(v_idx)-m):
    for cc in c:
        a[cc[0]][cc[1]]='*'
    tmp = bfs_check()
    if tmp < ans:
        ans = tmp
    for cc in c:
        a[cc[0]][cc[1]]=2
if ans ==987654321:
    print(-1)
else:
    print(ans)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static class Pair {
        public int x;
        public int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return x + "," + y;
        }
    }

    static class Comb {
        public ArrayList<Pair> candidate;
        public ArrayList<ArrayList<Pair>> candidateList;
        public ArrayList<Pair> sum;

        public Comb() {
            this.candidate = new ArrayList<Pair>();
            this.candidateList = new ArrayList<ArrayList<Pair>>();
            this.sum = new ArrayList<Pair>();
        }

        public void genComb(int idx, int m) {
            if (sum.size() == m) {
                ArrayList<Pair> tmp = new ArrayList<Pair>();
                for (Pair p : sum) {
                    tmp.add(p);
                }
                candidateList.add(tmp);
            } else if (idx < candidate.size()) {
                sum.add(candidate.get(idx));
                genComb(idx + 1, m);
                sum.remove(candidate.get(idx));
                genComb(idx + 1, m);
            }
        }
    }

    public static int bfs(int[][] lab2){
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,1,-1};


        Queue<Pair> q = new LinkedList<Pair>();
        int n = lab2.length;
        int[][] visited = new int[n][n];
        int ret = -1;

        int[][] lab = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                lab[i][j] = lab2[i][j];
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(lab[i][j]==2){
                    q.offer(new Pair(i,j));
                    lab[i][j]=0;
                    visited[i][j]=1;
                }
            }
        }

        while(!q.isEmpty()){
            Pair p = q.poll();

            int cnt = lab[p.x][p.y];

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(0<=nx && n>nx && 0<=ny && n>ny && visited[nx][ny]==0
                && (lab[nx][ny]==0 || lab[nx][ny]==-1)){
                    q.offer(new Pair(nx,ny));
                    lab[nx][ny] = cnt+1;
                    visited[nx][ny]=1;
                }
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(lab[i][j]==0 && visited[i][j]==0){
                    return -1;
                }
                if(lab2[i][j]!=-1 && visited[i][j]==1 && ret<lab[i][j]){
                    ret = lab[i][j];
                }
            }
        }

        return ret;


    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Comb comb = new Comb();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] lab = new int[n][n];
        int answer = 987654321;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
                if (lab[i][j] == 2) {
                    comb.candidate.add(new Pair(i, j));
                }
            }
        }

        comb.genComb(0, comb.candidate.size() - m);

        for (ArrayList<Pair> cand : comb.candidateList) {

            for (Pair p : cand) {
                lab[p.x][p.y] = -1;
            }

            int tmp = bfs(lab);

            if(tmp!=-1 && tmp < answer){
                answer = tmp;
            }

            for (Pair p : cand) {
                lab[p.x][p.y] = 2;
            }

        }
        if(answer == 987654321)
        {System.out.println(-1);}
        else{
            System.out.println(answer);
        }
    }
}