백준 삼성 코딩 기출 문제 - 연구소 python

백준 삼성 코딩 기출 문제 - 연구소 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] 최종적으로 전체 안전 영역에서 최소의 바이러스수를 빼버리면 정답을 구할 수 있습니다.

print(safe-num_virus)

전체 코드

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)