코딩 테스트 - 연구소 2023/05/20

성시영·2023년 5월 20일

DFS/BFS 골드 백준 코딩테스트

코딩테스트

목록 보기

1/1

문제 소개

연구소 (14502, 골드 4)

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

시간 제한: 2초
메모리 제한 : 512MB

연구소의 크기는 NXM인 직사각형이며, 직사각형은 1x1 크기의 정사각형으로 이루어져있다. 각 정사각형은 빈칸이거나 벽이다. 일부 빈칸에는 바이러스가 존재하며 상하좌우로 인접한 빈칸으로 확산한다. 새로 세울 수 있는 벽은 3개이며, 꼭 3개를 세워야한다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

0은 빈칸, 1은 벽, 2는 바이러스를 의미한다. 벽을 세워 안전 영역의 크기의 최대값을 구해라.

입력
첫째 줄에는 지도의 세로크기 n과 가로 크기 m이 주어진다 (3 <= n,m <=8)
둘째 줄부터 N개의 줄에 지도 모양이 입력된다. (2 <= 바이러스의 개수 <=10)
빈칸의 개수는 3개 이상이다.

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

출력
얻을 수 있는 안전 영역의 최대 크기를 출력

문제 이해 및 해결 방안

해당 문제는 바이러스가 위치한 곳을 격리하기 위해 벽을 세워 확산되지 않도록 하는 경우의 수 중 빈칸의 크기를 최대를 구하는 문제이다.
바이러스의 확산을 막는 경우의 수는 상당히 많다. 단순히 바이러스의 상하좌우를 막는 게 아니라 3개의 벽을 세워 빈칸을 확보하는 문제다. 즉, 바이러스는 벽으로 둘러쌓여 있지만 벽으로 격리한 공간에 빈칸이 들어갈 수 있다.
따라서 벽을 세울 수 있는 모든 경우의 수를 검토해야만 한다. 따라서 완전 탐색을 이용해야 한다.
벽이 세워진 경우에 바이러스의 확산이 이루어지고 빈 칸을 카운트해서 최대 값을 알아내야 한다. 이때 BFS나 DFS 알고리즘을 이용해 바이러스의 확산을 구현한다.

내가 작성한 코드

import sys
input=sys.stdin.readline #데이터 입력의 빠른 처리를 위해 사용
from collections import deque #BFS를 사용하기 위해 큐를 사용하는데 deque를 통해 시간을 단축시킬 수 있다.
import copy

n,m=map(int,input().split())
lab=[] #연구소
wallp=[] #빈칸의 좌표를 저장하는 리스트
virus=[] # 바이러스의 좌표를 저장하는 리스트
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(n):
    lab.append(list(map(int,input().split())))
    for j in range(m):
        if lab[i][j] ==0:
            wallp.append((i,j))
        elif lab[i][j] ==2:
            virus.append((i,j))
            
def bfs(lab):
    q=deque(virus)
    while q:
        x,y=q.popleft()
        
        for i in range(4):
            nx = x +dx[i]
            ny = y +dy[i]
            if nx <0 or nx>=n or ny<0 or ny>=m or lab[nx][ny] !=0:
                continue
            lab[nx][ny]=2
            q.append((nx,ny))

    val=0
    for i in range(n): #빈카의 개수 카운트
        for j in range(m):
            if lab[i][j]== 0:
                val+=1
    return val
 
answer=0
for i in range(len(wallp)-2):
    for j in range(i+1,len(wallp)-1):
        for w in range(j+1,len(wallp)): #연구소의 빈칸에 벽을 세워보는 모든 경우의 수를 고려
            x1,y1=wallp[i]; x2,y2=wallp[j]; x3,y3=wallp[w]
            if lab[x1][y1]!=0 or lab[x2][y2]!=0 or lab[x3][y3]!=0: #만약 벽을 세우려는 장소에 바이러스나 벽이 있다면 건너뛴다.
                continue
            tmplab=copy.deepcopy(lab)# 바이러스 확산이 원래의 연구소에 영향을 미치면 안되므로 임시 연구소를 생성
            tmplab[x1][y1]=1; tmplab[x2][y2]=1; tmplab[x3][y3]=1 #임시 연수소에 벽을 세운다.
            tmp=bfs(tmplab)
            if answer<tmp: #빈칸의 개수가 지금까지의 최대값 보다 크다면 정답 값 갱신
                answer=tmp
                
print(answer)

tmplab=copy.deepcopy(lab)를 통해 연구소의 코드를 복사한 이유는 파이썬은 얕은 복사를 기본으로 하기 때문이다. 값을 복사하지않고 참조만 하기 때문에 deepcopy함수를 통해 값을 복사해 기존의 연구소 리스트에는 영향을 주지 않도록 했다.
시간이 꽤 처참했다.

다른 사람의 코드를 기반으로 다시 작성한 코드

import sys
from collections import deque
from itertools import combinations


input=sys.stdin.readline

n,m=map(int,input().split())
lab=[]
wallp=[]
virus=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(n):
    lab.append(list(map(int,input().split())))
    for j in range(m):
        if lab[i][j] ==0:
            wallp.append((i,j))
        elif lab[i][j] ==2:
            virus.append((i,j))

    
 
answer=0
leng=len(wallp)
for combi in combinations(wallp,3):
    tmplab=[arr[:] for arr in lab]
    for x1,y1 in combi:
        tmplab[x1][y1]=1
    q=deque(virus)
    tmp_leng=leng-3
    while q:
        x,y=q.popleft()
        if answer > tmp_leng:
            break
        
        for i in range(4):
            nx = x +dx[i]
            ny = y +dy[i]
            if 0<= nx < n and 0<= ny < m and tmplab[nx][ny] ==0:
                tmplab[nx][ny]=2
                q.append((nx,ny))
                tmp_leng-=1
    answer = max(answer,tmp_leng)
                
print(answer)

시간에서 가장 큰 영향을 주었던 코드는 2개이다.

#기존의 코드
tmplab=copy.deepcopy(lab)
#바뀐 코드
tmplab=[arr[:] for arr in lab]

둘 다 파이썬에서 깊은 복사를 구현하는 코드이다. 하지만 아래의 코드가 더욱 빠르고 copy를 import할 필요가 없다.
일반적으로 슬라이싱은 기존의 리스트와 다른 새로운 리스트를 만들어 변수에 넣어준다.

b=[1,2,[3,4,5]]
a=b[:]
a[0]=9
#결과값
a=[9,2,[3,4,5]], b=[1,2,[3,4,5]]

예를 들어 b=[1,2,[3,4,5]]이라는 리스트를 a=b[:]의 형태로 슬라이싱 할 경우, a와 b는 다른 리스트로 a[0]=9로 바꾼어도 b는 영향을 받지 않는다. 즉, a=[9,2,[3,4,5]] , b=[1,2,[3,4,5]]의 결과를 가진다.

a[2].append(1)

#결과값
a=[1,2,[3,4,5,1]], b=[1,2,[3,4,5,1]]

하지만 a[2].append(1)을 했을 경우에는 a와 b 모두 [1,2,[3,4,5,1]]로 값이 바뀌게 된다. 그 이유는 a의 원소 [3,4,5]와 b의 원소 [3,4,5]가 같은 리스트를 가리키기 때문이다.

tmplab=[arr[:] for arr in lab]은 리스트 컴프리헨션을 통해 그 안의 리스트를 슬라이싱해서 리스트안의 리스트까지 서로 다른 리스트를 만드는 방법이다.

#기존의 코드
x1,y1=wallp[i]; x2,y2=wallp[j]; x3,y3=wallp[w]
(...)
tmplab[x1][y1]=1; tmplab[x2][y2]=1; tmplab[x3][y3]=1
#바뀐 코드
for x1,y1 in combi:
        tmplab[x1][y1]=1

(...)을 제외한 두개의 코드를 바꾸었을 때보다 아래의 코드가 더욱 시간이 짧고 가독성도 좋다.
그외에도 combinations, 빈칸의 개수를 계산하는 방법, BFS 도중 이미 답보다 작은 값은 작업을 멈추는 부분에서 속도 차이를 만들고 있었다.

느낀점

문제를 맞추긴 했으나 시간도 오래 걸리고 코드의 가독성이 좋지 않아 불만족스러웠다. 파이썬을 사용하고 있지만 파이썬이 가지는 장점(편리성)을 잘 살리지 못하는 것같다. 이로 인해 코드의 가독성도 떨어지고 비효율적인 코드를 작성하는 것 같다. 파이썬에서 제공하는 편리한 문법들에 대해 더 공부해야 겠다는 생각이 든다.
문제를 풀기 전에 어떻게 문제를 풀 것인가에 대해 고민하는 시간이 부족해 문제를 비효율적으로 접근하는 것 같다. 또한, 문제를 풀기 전 시간복잡도나 공간 복잡도를 고려하는 것도 미숙한 것 같다.

결론

문제를 풀기 전에 충분히 생각하자. 그리고 파이썬의 문법이나 시간 복잡도와 공간 복잡도에 대해 더 공부해야 겠다.

성시영

코딩 테스트 - 연구소 2023/05/20