[백준 14502번] 연구소 - 파이썬

문제 링크:

 

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

14502번: 연구소

 

백준 14502번 연구소 문제는 삼성 SW 역량테스트 기출문제이다.

 

백준 14502번 연구소 파이썬

 

---

풀이 유형:

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 구현

 

풀이  과정: 

이 문제는 벽을 3개 설치하는 모든 경우의 수를 다 계산해야 한다.

전체 맵의 크기가 최대 8 x 8이므로, 벽을 설치할 수 있는 최악의 경우 64C3이다. 

이는 100,000보다 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간 안에 문제를 해결할 수 있다.

이 문제는 다음 2가지 방법을 사용할 수 있다. 이 중 2번 방법을 이용해보겠다.

 

1. 파이썬의 조합 라이브러리(from itertools import combinations) 이용

2. DFS or BFS 이용

 

<풀이 순서>

1. DFS를 이용해 바이러스가 확산되도록 하는 함수를 만든다.
2. 안전거리 영역에 해당하는 점수를 세는 함수를 만든다.
3. DFS를 이용해 벽 3개를 설치하는 모든 경우의 수를 계산한다.
3-1. 벽을 3개 설치했다면 바이러스를 퍼뜨리고, 각 경우의 수(벽 3개)마다 비교하며 안전 영역의 최댓값을 계산한다.
4. DFS를 실행한 다음, 결과값을 출력한다.

풀이 코드:

 

# 14502번 연구소

# 1. 바이러스 퍼뜨리는 함수
# 2. 점수를 세는 함수
# 3. 벽 세우는 함수

from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())

data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

# 지도 모양 입력받기
for _ in range(n):
  data.append(list(map(int, stdin.readline().rstrip().split())))

# 북, 동, 남, 서 4가지 이동 방향 
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 바이러스 유출
def virus(x, y):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
    if 0 <= nx < n and 0 <= ny < m:
      if temp[nx][ny] == 0:
        # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
        temp[nx][ny] = 2
        virus(nx, ny)
  return

# 현재 맵에서 안전 영역의 크기를 계산하는 메서드
def get_score():
  score = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        score += 1
  return score

# 벽을 설치하면서 매번 안전 거리 계산
def dfs(count):
  global result
  # 벽이 총 3개인 경우
  if count == 3:
    for i in range(n):
      for j in range(m):
        temp[i][j] = data[i][j]
    # 각 바이러스의 위치에서 전파 진행
    for i in range(n):
      for j in range(m):
      	# 현 위치에 바이러스가 있다면 바이러스 확산
        if temp[i][j] == 2:
          virus(i, j)
    # 안전영역의 최댓값 계산
    result = max(result, get_score())
    return
  # 빈 공간에 벽 설치	
  for i in range(n):
    for j in range(m):
      if data[i][j] == 0:
        data[i][j] = 1
        count += 1
        # dfs함수 재귀적으로 수행
        dfs(count)
        data[i][j] = 0
        count -= 1

# dfs 실행
dfs(0)
# 안전영역의 최댓값 결과 출력
print(result)

 

 

14502번 연구소