연구소 3

아이디어

• M개의 바이러스로 이루어진 조합을 만듬
• 만들어진 바이러스 조합을 이용하여 각각의 경우에서 bfs 탐색

구현 방법

• 조합
  • 순열을 만들때의 함수를 변형하여 만듬
• bfs
  • deque에 집어넣을때 time 정보까지 같이 넣어줌
  • Time 정보를 visited에 표시
    • visited에 표시하는 이유는 탐색이 끝났을때 갈 수 있음에도 못가는 곳이 있으면 -1을 출력하기 위함
• Time check
  • 최소 시간을 찾으면서 갈수 있음에도 더이상 못가는 곳이 있으면 false 출력

어려웠던점

• Time check함수에서 max가 0일때 return 값이 false와 같다고 인식하여 답이 다르게 나옴

  • max+1 을 리턴해주고 밖에서 false true 판별 후 -1해줌

  • 파이썬에서 false 도 0으로 인식함

• 조합에 없는 바이러스를 만났을때 평소대로였으면 탐색 안한다고 생각하였음

  • 바이러스가 벽으로 인식되기 때문에 뒤에 더 갈 수 있을 경우엔 이를 탐색하지 못함

  • 바이러스를 지날때는 time 정보는 그대로 +1을 해주고 visited에 0을 넣어 바이러스임을 표시함

  • visited 0을 바이러스 위치로 표시하였으므로 -1로 초기화하여 방문 지점과 방문하지 않은 곳을 구별

코드

• python

from _collections import deque


def find():
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 2:
                virus.append((i,j))

def combination(index):
    if index == M:
        temp = a[:]
        comb.append(temp)
    else:
        in_perm = [False]*n
        for i in range(index):
            in_perm[a[i]] = True
        for i in range(n-1,-1,-1):
            if in_perm[i]:
                posi = i + 1
                break
        else:
            posi = 0
        c = [0] * n
        cnt = 0
        for i in range(posi,n):
            if not in_perm[i]:
                c[cnt] = i
                cnt += 1
        for i in range(cnt):
            a[index] = c[i]
            combination(index+1)

def time_check():
    max = -1
    isSuccess = True
    for y in range(N):
        for x in range(N):
            if visited[y][x] > max:
                max = visited[y][x]
            elif visited[y][x] == -1 and not matrix[y][x]:
                isSuccess = False
    if isSuccess:
        return max+1
    else:
        return isSuccess

def bfs():
    while deq:
        here = deq.popleft()
        y, x, time = here[0], here[1], here[2]
        for dir in range(4):
            ny, nx = y + direct[dir][0], x + direct[dir][1]
            if 0 <= ny < N and 0 <= nx < N and matrix[ny][nx] == 2 and visited[ny][nx] == -1:
                deq.append((ny,nx,time+1))
                visited[ny][nx] = 0
            elif 0 <= ny < N and 0 <= nx < N and not matrix[ny][nx] and visited[ny][nx] == -1:
                deq.append((ny,nx,time+1))
                visited[ny][nx] = time+1

direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
virus = []
find()
n = len(virus)
a = [0] * M
comb = []
combination(0)
min = 987654321
isFail = True
for idx in range(len(comb)):
    deq = deque()
    visited = [[-1]*N for _ in range(N)]
    for i in range(M):
        y,x = virus[comb[idx][i]][0],virus[comb[idx][i]][1]
        deq.append((y,x,0))
        visited[y][x] = 0
    bfs()
    ans = time_check()
    if ans and ans-1 < min:
        min = ans-1
        isFail = False
else:
    if isFail:
        print(-1)
    else:
        print(min)

• java

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

public class Main17142_연구소3 {
	static int N, M;
	static int[][] matrix;
	static int[][] direct = {
			{-1,0},
			{0,1},
			{1,0},
			{0,-1},
	};
	static int[][] comb;
	static int[] a;
	static int[][] virus;
	static int virusCount = 0;
	static int top = 0;
	static int[][] visited;
	static Queue<int[] > q;
	
	public static void combination(int index, int[] a) {
		if (index == M) {
			int[] temp = new int[M];
			for (int i=0; i<M; i++) {
				temp[i] = a[i];
			}
			for (int i=0; i<M; i++) {
				comb[top][i] = temp[i];
			}
			top ++;
		} else {
			int posi = 0;
			int cnt = 0;
			boolean[] inComb = new boolean[virusCount];
			for (int i=0; i<index; i++) {
				inComb[a[i]] = true;
			}
			for (int i=virusCount-1; i>-1; i--) {
				if (inComb[i]) {
					posi = i+1;
					break;
				}
			}
			int[] c = new int[virusCount];
			for (int i=posi; i<virusCount; i++) {
				if (!inComb[i]) {
					c[cnt] = i;
					cnt ++;
				}
			}
			for (int i=0; i<cnt; i++) {
				a[index] = c[i];
				combination(index+1, a);
			}
			
		}
	}
	
	public static void bfs() {
		int y, x, ny, nx, time;
		while (!q.isEmpty()) {
			int[] here = q.poll();
			time = here[2];
			for (int dir=0; dir<4; dir++) {
				ny = here[0] + direct[dir][0];
				nx = here[1] + direct[dir][1];
				if (0 <= ny && ny < N && 0 <= nx && nx < N && matrix[ny][nx] == 2 && visited[ny][nx] == -1) {
					q.offer(new int[] {ny,nx,time+1});
					visited[ny][nx] = 0;
				} else if (0 <= ny && ny < N && 0 <= nx && nx < N && matrix[ny][nx] == 0 && visited[ny][nx] == -1) {
					q.offer(new int[] {ny,nx,time+1});
					visited[ny][nx] = time + 1;
				}
			}
		}
	}
	
	public static int timeCheck() {
		int max = -1;
		boolean isSuccess = true;
		for (int r=0; r<N; r++) {
			for (int c=0; c<N; c++) {
				if (visited[r][c] > max) {
					max = visited[r][c];
				} else if (visited[r][c] == -1 && matrix[r][c] == 0) {
					isSuccess = false;
					max = -1;
					break;
				}
			}
			if (!isSuccess) {
				break;
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new int[N][N];
		virus = new int[10][2];
		int y, x, ans;
		int min = 987654321;
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				if (matrix[i][j] == 2) {
					virus[virusCount][0] = i;
					virus[virusCount][1] = j;
					virusCount ++;
				}
			}
		}
		
		comb = new int[10000][M];
		a = new int[M];
		combination(0, a);
		
		for (int i=0; i<top; i++) {
			q = new LinkedList<>();
			visited = new int[N][N];
			for (int r=0; r<N; r++) {
				for (int c=0; c<N; c++) {
					visited[r][c] = -1;
				}
			}
			for (int j=0; j<M; j++) {
				y = virus[comb[i][j]][0];
				x = virus[comb[i][j]][1];
				q.offer(new int[] {y,x,0});
			}
			bfs();
			ans = timeCheck();
			if (ans > -1 && ans < min) {
				min = ans;
			}
		}
		if (min==987654321) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}
	}

}