[Python Algorithm] 연구소 BOJ #14502

문제

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

14502번: 연구소

 

내 문제 풀이

import copy

n, m = map(int, input().split())
space = [] # 문제에서 주어진 지도
virusSpace = [] # 바이러스의 위치

""" 입력 """
for i in range(n):
    space.append(list(map(lambda x: int(x), input().split())))
    for j in range(m):
        if space[i][j] == 2:
            virusSpace.append((i, j))

check = copy.deepcopy(space)
result = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

""" 바이러스 전파 """
def dfs(x, y, check):
    if check[x][y] == 2:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m: continue

            if check[nx][ny] == 0:
                check[nx][ny] = 2
                dfs(nx, ny, check)

""" 벽 세우는 모든 경우의 수 탐색 """
def makeWall(start, count):
    global result
    safe_count = 0

    if count == 3:
        check = copy.deepcopy(space)
        for i in virusSpace:
            dfs(i[0], i[1], check)

        for i in range(n):
            safe_count += check[i].count(0)
        result = max(result, safe_count)
        return

    else:
        for i in range(start, n*m):
            x = i // m
            y = i % m
            if space[x][y] == 0:
                space[x][y] = 1
                makeWall(i, count+1)
                space[x][y] = 0

makeWall(0, 0)
print(result)

👉 브루트포스/DFS 문제로, 벽을 세우는 모든 경우의 수를 구하고, 경우마다 바이러스가 전파되는 것을 체크해주었다.

• makeWall 함수를 보면, 벽을 총 3개 세워야 하므로 count가 3이 되기 전까지 벽을 세웠다.
  else 조건문의 for문을 통해 지도의 모든 자리를 탐색해주었는데,
  자리가 0인 곳을 발견하면 벽을 세운 후 makeWall을 재귀호출하는 방법을 사용했다.
  재귀호출할 때는 탐색 시작 점을 i로 해주고, count를 증가시켜주었고,
  호출이 끝나면 벽을 세웠던 자리는 다시 0을 저장하여 복구시켰다.
  count가 3이 되었을 때는 3개의 벽을 세운 space 리스트를 check에 넣고,
  미리 만들어 놓은 virusSpace 리스트를 돌며 바이러스가 있는 곳마다를
  시작점으로 생각하여 dfs 함수를 호출해주었다.
  dfs 함수 실행이 종료되면 0의 개수를 세고, result와 비교해서 큰 값을 저장했다.
• dfs 함수는 파라미터로 입력받은 좌표를 기준으로 바이러스를 전파시키는 함수이다.
  바이러스를 기준으로 상하좌우를 탐색하고, 범위를 벗어날 경우를 제외하여
  0이 저장된 자리를 2로 바꿔주었다. 그리고 그 자리를 파라미터로 넣어 dfs를 재귀호출했다.

 

💡 피드백

• 어렵지 않은 문제였지만 순전히 파이썬이라 푸는데 오래걸렸다.
  일단 나는 deepcopy를 몰라서 그걸 해결하는데에 아주 오래걸렸다.
  공부가 필요할 것 같다.