백준 삼성 코딩 기출 문제 - 연구소 python
출처 : BAEKJOON ONLINE JUDGE
연구소 (https://www.acmicpc.net/problem/14502)
문제 설명
연구소 NxM 크기에 빈 칸(0), 벽(1) 그리고 바이러스(2)가 있습니다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나갑니다. 새로 세울 수 있는 벽은 3개로 고정됩니다. 무조건 3개를 세워야합니다. 벽을 3개 세운 뒤에 바이러스가 퍼질 수 없는 곳이 안전 영역입니다. 안전 영역 크기(칸의 개수)의 최대값을 구하는 것이 문제입니다.
문제 풀이
이 문제는 DFS로 접근합니다. DFS(Depth First Search) 알고리즘은 stack(LIFO)과 재귀 함수를 사용해 구현해야 합니다.
[1] 입력을 받습니다.
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)] |
[2] 방문 칸에 대해서 체크를 하고, virus의 (x,y) 좌표를 저장합니다.
visited = [[False]*m for _ in range(n)] # dfs 방문한 여부
virus = [] # virus (x,y) 좌표
num_virus = 9999 # 최종적으로 퍼져나간 virus 개수
safe = -3 # 벽을 3개 꼭 세워야함. |
[3] 위에서 입력 받은 값을 통해서 virus를 넣고, 벽이 아닌 공간들은 우선 안전한 영역의 칸 수로 저장합니다.
for i in range(n):
for j in range(m):
if board[i][j] != 1: # 벽이 아니라면,
safe += 1
if board[i][j] == 2: # virus라면
virus.append((i, j)) |
[4] 바이러스가 확장되는 것을 dfs()를 통해서 구현합니다. 입력값 x,y를 받게되며, 바이러스로 퍼진 개수를 반환합니다.
- x, y 좌표에 대해 방문 여부를 체크 합니다.
- 상하좌우로 4방향으로 이동합니다. 이동하는 값을 dx, dy에 넣고 다음 x,y 좌표를 계산합니다.
- 연구소(맵)의 크기를 벗어나는 경우에 대해서 확인하기 위해 경계보다 커지면 continue 문으로 넘어갑니다.
- 방문하지 않았거나, 빈칸이 아니라면(벽도 아니고, 바이러스도 아니기 때문에) 바이러스가 퍼질 수 있습니다 -> 재귀적으로 호출합니다.
- 최종적으로 퍼진 바이러스의 개수를 반환합니다.
def dfs(x, y): # virus를 퍼뜨린다.
n_virus = 1 # 바이러스 개수
visited[x][y] = True # 방문 여부 체크
for dx, dy in (-1,0), (1,0), (0,-1), (0,1): # 위, 아래, 좌, 우
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_x >= n or next_y < 0 or next_y >= m: # 맵의 경계보다 커진다면
continue # 넘어간다.
if not (visited[next_x][next_y] or board[next_x][next_y]): # 방문하지 않았거나, 빈칸이 아니라면
n_virus += dfs(next_x, next_y)
return n_virus |
[5] 전체 연구소의 맵에서 벽을 3개씩 세워보면서 살펴봅니다.
- 벽이 이미 세 개라면, 주어진 바이러스 개수 만큼 바이러스가 퍼지는 것을 시뮬레이션하는 dfs()를 호출하고, 바이러스가 제일 적은 경우를 결과에 저장합니다.
- 주어진 맵에서 x, y좌표로 벽을 세워봅니다. 2차원 배열에서 x, y의 조합을 뽑습니다.
- 현재 x,y의 위치가 빈칸이라면 벽(1)을 세우고, solve()를 재귀적으로 호출합니다. 호출이 끝나면 세운 벽을 다시 빈칸(0)으로 만듭니다.
def solve(start, wall): # 벽을 세우는 함수
global n, m, num_virus, visited
if wall == 3: # 벽이 3개라면
n_virus = 0
visited = [[False]*m for _ in range(n)]
for x, y in virus: # 주어진 바이러스에 대해 바이러스가 퍼지는 것을 시뮬레이션한다.
n_virus += dfs(x, y)
num_virus = min(num_virus, n_virus) # 바이러스가 제일 적은 경우를 저장한다.
return
for i in range(start, n*m): # 2차원 배열에서 x, y의 조합을 뽑습니다.
x = i // m
y = int(i % m)
if board[x][y] == 0: # 빈칸(0) 이라면
board[x][y] = 1 # 벽(1)을 세운다
solve(i+1, wall+1)
board[x][y] = 0 # 위에서 세운 벽을 다시 빈칸(0)으로 만든다. (초기화) |
[6] 최종적으로 전체 안전 영역에서 최소의 바이러스수를 빼버리면 정답을 구할 수 있습니다.
전체 코드
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
virus = []
num_virus = 9999
safe = -3 # 벽을 3개 꼭 세워야함.
def dfs(x, y): # virus를 퍼뜨린다.
res = 1
visited[x][y] = True
for dx, dy in (-1,0), (1,0), (0,-1), (0,1): # 위, 아래, 좌, 우
nx, ny = x+dx, y+dy
if nx < 0 or nx >= n or ny < 0 or ny >= m: # 맵의 경계보다 커진다면
continue # 넘어간다.
if not (visited[nx][ny] or board[nx][ny]): # 방문하지 않았거나, 빈칸이 아니라면
res += dfs(nx, ny)
return res
def solve(start, wall): # 벽을 세운다
global n, m, num_virus, visited
if wall == 3: # 벽이 3개라면
count = 0
visited = [[False]*m for _ in range(n)]
for x, y in virus:
count += dfs(x, y)
num_virus = min(num_virus, count)
return
for i in range(start, n*m): # 2차원 배열에서 x, y의 조합을 뽑습니다.
x = i // m
y = int(i % m)
if board[x][y] == 0: # 빈칸(0) 이라면
board[x][y] = 1 # 벽(1)을 세운다
solve(i+1, wall+1)
board[x][y] = 0 # 위에서 세운 벽을 다시 빈칸(0)으로 만든다. (초기화)
for i in range(n):
for j in range(m):
if board[i][j] != 1: # 벽이 아니라면,
safe += 1
if board[i][j] == 2: # virus라면
virus.append((i, j))
solve(0, 0)
print(safe - num_virus) |
