[dfs/bfs] 연구소
문제
- 크기가 N X M인 연구소
- 0 : 공간, 1 : 벽, 2 : 바이러스
- 바이러스는 상하좌우의 칸으로 퍼져나갈 수 있음
- 벽을 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 |
27 |
정답
# ============= [0] ================
n,m = map(int,input().split())
data = []
temp = [[0] * m for _ in range(n)]
for _ in range(n):
data.append(list(map(int,input().split())))
dx=[0,1,0,-1]
dy=[-1,0,1,0]
result = 0
# ============= [1] ================
def virus(x,y):
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0 <= nx < n and 0 <= ny < m:
if temp[nx][ny] == 0:
temp[nx][ny] = 2
virus(nx,ny)
# ============= [2] ================
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] ==0:
score+=1
return score
# ============= [3-1] ================
def dfs(count):
global result
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for i in range(n):
for j in range(m):
if temp[i][j]==2:
virus(i,j)
result = max(result, get_score())
return
# ============= [3-2] ================
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
dfs(count)
data[i][j] = 0
count -= 1
# ============= [4] ================
dfs(0)
print(result)
풀이
이 문제는 크게 세 가지 함수를 만들어 풀 수 있는 문제였다. (못풀어서 답지봄..)
1. 3개의 벽을 세우는 모든 경우의 수를 구해
2. 각각의 경우마다 바이러스를 퍼뜨리고
3. 그때의 안전구역의 크기를 구해서 이전의 안전구역과 비교한 후 더 큰 것을 갱신
나는 파이썬 문법에 익숙하지 않아서 구현할 때 많이 힘들었다.
그리고 경우의 수를 구할 때 파이썬 내장 모듈 itertools의 combination이라는 것도 알게 되었지만
사용하지 않고도 dfs로 풀 수 있는 문제였다.
# ============= [0] ================
n,m = map(int,input().split())
data = []
temp = [[0] * m for _ in range(n)]
for _ in range(n):
data.append(list(map(int,input().split())))
dx=[0,1,0,-1]
dy=[-1,0,1,0]
result = 0
여기서 data는 초기 입력받은 맵의 정보를 저장하는 리스트형 변수이고,
temp는 각각의 경우의 수를 돌 때마다 data의 정보를 새로 받아서 맵을 초기화시키는 역할을 하는 변수이다.
처음에 맵을 돌면서 0이면 2로 바꿔서 바이러스를 퍼뜨리거나, 0을 1로 바꿔 벽을 세워야 한다는 생각은 했었는데,
그러면 다음 경우의 수를 돌 때는 수정된 맵을 탐색하게 되어버려서 난감했다.
결론적으로는 처음 입력받은 맵정보를 저장할 리스트와,
그걸 매번 새로 갖다 쓸 리스트가 두 개 있어야 한다는 점이 포인트였다.
# ============= [1] ================
def virus(x,y):
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0 <= nx < n and 0 <= ny < m:
if temp[nx][ny] == 0:
temp[nx][ny] = 2
virus(nx,ny)
각 경우의 수마다 바이러스를 퍼뜨리는 함수.
처음 바이러스가 존재하는 좌표 (x,y)를 받아서
상하좌우 네 방향을 dfs로 탐색해나가면서 연결된 모든 0들을 2로 바꾼다.(바이러스를 퍼뜨리는 것을 의미)
# ============= [2] ================
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] ==0:
score+=1
return score
안전구역의 크기를 구하는 함수.
바이러스를 퍼뜨리고 나서 이 함수를 호출하여 각 경우의 수마다 안전구역의 크기를 계산할 수 있다
# ============= [3-1] ================
def dfs(count):
global result
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for i in range(n):
for j in range(m):
if temp[i][j]==2:
virus(i,j)
result = max(result, get_score())
returnglobal
파이썬에서 사용하는 global 변수.
전역변수를 함수 내에서 사용하고 싶을 때에는
global을 앞에 붙여줘야 전역변수로 선언된 result를 쓰는거구나 하고 알 수 있고,
만약 붙여주지 않고 그냥 result라고 써버린다면
전역으로선언된 result와 상관없는 새로운 지역변수 result가 생성되는 것임
count는 세워진 벽의 개수를 의미.
벽이 3개 세워져있다면 초기의 맵정보인 data를 복사해와서 바이러스가 있는 좌표(x,y) 를 virus() 함수에 넘겨줌
virus함수는 === [1] === 파트에서 언급했지만
상하좌우 네 방향을 dfs로 탐색해나가면서 연결된 모든 0들을 2로 바꾸는 작업을 통해 바이러스를 퍼뜨림
바이러스가 퍼졌으면 나머지 안전구역을 get_score() 함수로 구하고
최대값을 갱신하기 위해 이전의 result값과 비교해서 큰 값을 result에 새로 저장하게 됨
(이 때, 처음 result는 0으로 선언 및 초기화를 해 놨음)
# ============= [3-2] ================
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
dfs(count)
data[i][j] = 0
count -= 1
벽을 3개 생성하는 로직.
data[i][j] == 0 이면 1로 바꾸고 (벽생성)
dfs(count)를 재귀호출함으로써 count(벽 개수) == 3이 될때까지 0을 3개 찾아 1로 바꾸는 작업을 진행.
그리고 여기서 중요한 점은 마지막 2줄
data[i][j] = 0
count == 1
에서
data 변수는 초기의 맵 정보를 담고 있는 변수이기 때문에 dfs를 재귀호출 한 후
다시 바꿔줬던 값을 0으로 되돌리는 작업을 수행해야 함
(내가 해석한 게 정확한지는 모르겠지만 난 이런 이유라고 생각했음)
# ============= [4] ================
dfs(0)
print(result)그리고 처음 벽의 개수인 0을 매개변수로 dfs 함수를 호출하면
자동으로 전역변수인 result값이 갱신될 것임
참조
- 이것이 취업을 위한 코딩테스트다. with 파이썬