[백준 14502] 연구소 (python)

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

14502번: 연구소

연구소 문제

BFS를 이용한 구현을 섞어놓은 문제라 여러모로 시도해보기 좋은 문제

내가 푼 정답 코드

def walls(n, m): # 벽 3개 골라보자
    global clean
    if m == 3: # 벽 3개 골랐으면
        maps_c = copy.deepcopy(maps) #벽 3개 칠한걸 임시로 복사하자
        for r,c in virus(): #바이러스에 대해
            finding(r,c,maps_c) #바이러스를 퍼뜨려보자
        cleans = sum(i.count(0) for i in maps_c) # 복사한 지도에서 0의 갯수를 세보자
        clean = max(clean,cleans) # 기존 값과 새로운 값중 큰거 저장해
        return True
    
    else : # 벽 3개 고르기
        for i in range(n, N*M): #전체 범위에서
            r = i//M 
            c = i% M
            if maps[r][c] == 0: # 빈공간 일 때
                maps[r][c] = 1 # 벽 세우기
                walls(i, m+1)
                maps[r][c] = 0

def finding(a,b, maps_c): #바이러스 퍼짐을 구현하기 위한 BFS
    move = [[1,0], [-1,0], [0,1], [0,-1]] #바이러스 퍼지는 움직임
    queue = [[a,b]]
    while queue:
        y, x = queue.pop(0)
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and maps_c[ny][nx] == 0:
                maps_c[ny][nx] = 2
                queue.append([ny,nx])

def virus(): # 시작 바이러스 위치를 찾자
    result = []
    for i in range(N):
        for j in range(M):
            if maps[i][j] == 2: # 2인 지점의 값을 저장
                result.append([i,j])
    return result

clean = 0

import sys
import copy
N, M = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
walls(0,0)
print(clean)

크게 요구조건이 3개이기 때문에 3가지로 나누어서 풀었다.

1. 바이러스가 점점 퍼져나가기 시작하니까, 바이러스의 시작 지점을 찾아줄 함수 virus를 만들어주었다. 결과값 하나씩 그냥 for문으로 돌려도 됐겠지만, 개인적으론 이렇게 나누는게 코드 짤 때 좋아서 나누었다.

2. 바이러스가 상하좌우로 퍼져나가기 시작하는 과정을 BFS로 구현해주었다. 굉장히 기본적인 BFS 코드 그대로 가져다가 넣었기에 어려움이 없었다.

3. 벽 3개를 세워주는 조건. 이게 가장 구현의 핵심이자 어려운 부분이 아닐까 싶다. 벽 3개를 고르는 과정을 재귀를 이용하여 구현해주었다. (wall 함수 내 else문) 벽을 3개 세우고 나서는 1,2 번을 이용하여 바이러스를 이동시켰고, 이때의 0의 갯수의 최대 값을 찾아서 출력해주는 형식으로 구성했다. 이 과정에서 연구소 지도(maps)를 유지한채로 넣어야하므로 깊은 복사를 통해 하나를 복사해서 거기에 시도해 보는 형식으로 코드를 짯다.

---

느낀점

전형적인 구현문제인데, 내가 구현을 하는거에 굉장히 약하기 때문에 꽤나 도전적인 문제였다. 대부분의 것을 구현하는데 성공했으나, 벽 3개를 세우는 부분이 가장 어려웠던거 같다. 벽 3개를 재귀를 통해 구현하는 점만 잘 만들어준다면 어렵지 않게 접근했을 수 있을거 같았는데 원하는대로 잘 안돼서 애먹었다.

최종적으로 구현에 성공하면서 굉장히 뿌듯함을 느꼇고, 구현하는 실력이 조금 늘어난걸 느꼈다.

아직 그래도 구현 기술이 부족하니 당분간은 구현에 좀 더 집중해서 공부해볼 생각이다