백준 17141 - 파이썬

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

17141번: 연구소 2

문제 풀이

이 문제는 삼성 sw 역량 테스트 기출 문제인 연구소3 문제를 풀다가 연구소3은 아직 풀기에 벅찬거 같아서 풀게 된 문제이다. 사실 연구소 2 역시 풀기에 벅찼다. 그래서 다른 사람의 블로그를 참고해 봤다.

 

문제 풀이의 포인트는 다음과 같다.

 

1. 그래프를 순회하며 바이러스의 위치를 담는다.

2. 바이러스의 위치를 담은 리스트를 m개의 조합으로 새로운 리스트에 담는다.

3. 조합된 리스트의 위치를 시작으로 bfs탐색을 한다.

4. max 함수를 이용하여 현재 경우의 수에서 가장 큰 수를 저장한다.(걸린 시간)

5. bfs함수를 리턴하여 가장 최근에 저장된 answer값과 비교하여 더 작은 수를 저장한다.(시간이 가장 최소가 되는 경우)

 

위에 나열된 포인트들을 코드로 구현하면 된다.

 

코드

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
virus = []

answer = float('inf')

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

def bfs(v):
  q = deque(v)
  visited = [[-1 for _ in range(n)] for _ in range(n)]
  m = 0
  for x,y in q:
    visited[x][y] = 0
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < n:
        if visited[nx][ny] == -1 and graph[nx][ny] != 1:
          q.append((nx,ny))
          visited[nx][ny] = visited[x][y] + 1
          m = max(m,visited[x][y] + 1)

  for i in range(n):
    for j in range(n):
      if visited[i][j] == -1 and graph[i][j] != 1:
        return float("inf")
        
  return m

for i in range(n):
  for j in range(n):
    if graph[i][j] == 2:
      virus.append((i,j))

for v in combinations(virus,m):
  print(v)
  answer = min(bfs(v), answer)

if answer == float('inf'):
  print(-1)
else:
  print(answer)

여기서 조합을 구하기 위해 combinations라는 함수를 사용하였는데, 자세한 내용은 해당 블로그를 참고하면 된다.

 

느낀점

아직 기출문제를 풀 정도의 실력은 안되는 거 같다. 그래도 떠올린 생각들이 정답과 크게 빗나가고 있지 않고, 아예 못 풀겠다는 느낌까지는 아니니 계속해서 꾸준히 노력해야 되겠다.