[BAEKJOON]14502 연구소 - Python

문제 요약

• 알고리즘 분류:BFS, 시뮬레이션
• 난이도: Gold4
• 문제내용:
  • 0은 길 1은 벽이다.
  • 벽은 한번 부수고 이동가능하다.
  • (0, 0) ~ (N, M)까지의 거리를 구해라
• 사이트: https://www.acmicpc.net/problem/14502

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다. 이번 문제는 가로세로 최대 길이가 8이라서 시간 복잡도에 제한은 없지만 구현난이도가 있어서 구현 하는 방법만 알면 쉽게 풀수 있다고 생각한다.

문제 접근방법

 처음에 재귀 호출을 하는데 벽을 3개 만든다고 (0, 0)부터 시작해서 4가지 방향 탐색한후 백트레킹 방식으로 돌아올때 벽을 빼고 하면 안된다.

  그 이유는  보면 (0, 0)부터 시작해서 벽을 치고 나중에  주황색 화살표 까지 위치한 다음 나머지 벽 없는 곳을 찾을라니까 주위에 다 벽이 있어서 진행을 못하는 경우가 생긴다. 그래서 0의 위치를 다 파악한 후에 위치 3개를 뽑는 조합으로 하면된다.  파이썬은 combination이라는 조합을 제공하는 함수가 있는데 다른 언어는 직접 구현해야 된다. 3개가 조합이 되면 BFS 탐색 방법으로 상화좌우 0인곳만 찾아서 진행한후 BFS 탐색이 끝나면 0의 개수를 새면 끝이다.

정리

1. 바이러스위치와 빈칸의 위치를 파악한다.
2. 빈칸을 위치를 조합으로 3개 추출한다.
3. 바이러스 위치에 큐를 저장한후 BFS 탐색해서 바이러스를 퍼트린다.
4. BFS 탐색후 빈칸 개수를 찾는다.

Code

Python

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

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

# 벽 세우기
def set_wall():
    count = 0
    for walls in combinations(cleans, 3):
        for x, y in walls:
            fields[x][y] = 1
        count = max(dfs(), count)
        for x, y in walls:
            fields[x][y] = 0
    return count


def dfs():
    # 연구도 지도와 viruse위치 가져 올때 깊은 복사로 처리 해야 한다. 값을 참조하기 때문에 dfs연산후 리스트에 반영 될수 있기 때문이다.
    matrix = copy.deepcopy(fields)
    queue = deque(copy.deepcopy(viruses))
    while queue:
        x, y = queue.popleft()
        # 바이러스 상하좌우로 퍼트리기
        for i in range(4):
            fx, fy = x + dx[i], y + dy[i]
            if 0<= fx <N and 0 <= fy < M and matrix[fx][fy] == 0:
                queue.append((fx, fy))
                matrix[fx][fy] = 2
    no_virus_count = 0
    #print("matrix")
    for array in matrix:
        #print(array)
        no_virus_count += array.count(0)
    return no_virus_count


N, M = map(int, input().split())
fields = [list(map(int, input().split())) for _ in range(N)]
viruses = []
cleans = []

# 바이러스 위치 찾기
for i in range(N):
    for j in range(M):
        if(fields[i][j] == 2):
            viruses.append((i, j))
        elif(fields[i][j] == 0):
            cleans.append((i, j))

print(set_wall())