백준 17142 - 연구소 3

백준 17142 - 연구소 3

https://www.acmicpc.net/problem/17142

삼성 기출 문제는 백트래킹을 활용하는 문제가 자주 출제되는 것 같다.

★ 풀이

삼성 기출 문제. 백트래킹, BFS사용

바이러스들 중 M개를 선택하는 조합들 중에서 가장 빠르게 바이러스를 퍼뜨리는 경우의 수가 존재하는 경우 시간을 출력하고, 없을 경우 -1을 출력한다.

바이러스들 중에서 M개를 선택해야 하므로 백트래킹으로 조합을 구하고, 맞춘 조합마다 BFS로 최소시간을 측정해서 답을 최신화 시키면 된다.

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 스킬 흡수하기 public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n,m,ans; static int board[][]; static int dist[][]; static boolean checked[]; static ArrayList virus; static final int INF = Integer.MAX_VALUE; static int dx[] = {0,1,0,-1}; static int dy[] = {1,0,-1,0}; public static void main(String[] args) throws IOException { StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); virus = new ArrayList<>(); board = new int[n][n]; for(int i = 0; i q = new LinkedList(); dist = new int[n][n]; boolean visited[][] = new boolean[n][n]; for(int i = 0; i= n || nx < 0 || ny >= n || ny < 0) continue; if(board[nx][ny] == 1) continue; if(dist[nx][ny] <= dist[v.x][v.y]) continue; if(visited[nx][ny]) continue; visited[nx][ny] = true; q.add(new Virus(nx,ny)); dist[nx][ny] = dist[v.x][v.y] + 1; } } ans = Math.min(checkTime(dist),ans); } static int checkTime(int dist[][]) { int ret = 0; for(int i = 0; i

from http://sweet-smell.tistory.com/166 by ccl(A) rewrite - 2021-12-17 16:27:51