[Python] 14502번. 연구소

문제 링크

성능 요약

메모리: 32412 KB, 시간: 1456 ms

분류

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

 

처음에 풀 때 자꾸 틀리길래 그 이유를 계속 못 찾다가 dfs 함수의 종료 순서 때문에 틀렸다는 것을 알게 되었다.

처음 짠 코드는

`#범위를 넘어서면`→ `#만약 벽을 3개 세웠다면`

해당 순서로 종료 조건을 주었는데 이렇게 되면 벽을 3개 다 세운 경우에도 `n >= len(loc0)`이면 BFS를 아예 안 돌고 종료돼서 ans가 갱신될 기회 자체가 없게 된다는 것을 알게 되었다.

`#만약 벽을 3개 세웠다면` → `#범위를 넘어서면`

순서로 종료 조건을 주어서 무사히 통과할 수 있었다.

이번 풀이를 통해 종료 조건의 순서 또한 중요하다는 것을 알 수 있었다.

"""
벽을 세울 수 있는 경우를 3개의 조합으로 만들어서 푼다
"""

#1.입력
N,M=map(int,input().split())
matrix=[list(map(int,input().split())) for _ in range(N)]

#2.추가 자료형 정의
loc0=[] #0의 위치
loc2=[] #2의 위치
for y in range(N):
    for x in range(M):
        if matrix[y][x]==0:
            loc0.append((y,x))
        if matrix[y][x]==2:
            loc2.append((y,x))
ans=0 #정답

#3.동작 알고리즘
dir=[(-1,0),(1,0),(0,-1),(0,1)]
def bfs():
    #바이러스 전염시키기
    queue=loc2[:]
    visited=[[False]*M for _ in range(N)]
    while queue:
        y,x=queue.pop(0)
        for dy,dx in dir:
            ny,nx=y+dy,x+dx
            if 0<=ny<N and 0<=nx<M:
                if matrix[ny][nx]==0 and not visited[ny][nx]:
                    visited[ny][nx]=True
                    queue.append((ny,nx))

    #전염 안된 곳 찾기
    cnt=0
    for y in range(N):
        for x in range(M):
            if matrix[y][x]==0 and not visited[y][x]:
                cnt+=1

    return cnt

def dfs(n,depth):
    global ans

    #만약 벽을 3개 세웠다면
    if depth==3:
        tmp=bfs()
        ans=max(tmp,ans)
        return
    
    #범위를 넘어서면
    if n>=len(loc0):
        return

    y,x=loc0[n]
    #1)선택하지 않는다
    dfs(n+1,depth)
    #2)선택한다
    matrix[y][x]=1
    dfs(n+1,depth+1)
    matrix[y][x]=0

dfs(0,0)

#4.출력
print(ans)