-
[백준 14502] 연구소 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2020. 11. 28. 19:58
문제 풀이
N, M, board : 입력값
virus : 바이러스 좌표 (x, y)
ans : 결과값(최대 빈 공간)
tmp_board : 원본 board를 훼손하지 않기 위해 복사
q : 바이러스 bfs를 위한 deque
bfs(board, virus) : 바이러스를 퍼트리기 위해 bfs로 탐색
다소 비효율적이긴 하지만 6중 for문을 통해 3개의 벽을 세우는 것을 구현하였다.
1. 3개의 서로 다른 벽 세우기 구현
6중 for문을 통해 벽 세우는 것을 구현한다.
이때 빈 공간이 아닐 경우와 3개 중 하나라도 같은 벽이 있을 경우 continue를 해준다.
2. bfs를 통해 바이러스를 퍼트린다.
바이러스가 동시에 퍼트려져야 하기 때문에 q의 사이즈만큼 반복문을 사용한다.
3. 바이러스가 퍼진 후 남아있는 빈 공간을 계산한다.
4. 1~3 과정을 모든 경우의 벽을 세울때까지 반복한다.
코드
import sys from collections import deque from copy import deepcopy def bfs(board, virus): dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] q = deque(virus) # 원본 board 훼손하지 않기 위해 deepcopy로 복사 tmp_board = deepcopy(board) tmp = 0 # bfs while q: size = len(q) # tmp_board 에 존재하는 바이러스를 동시에 퍼트리게 하기 위해 len(q) 만큼 반복문 실행 for _ in range(size): x, y = q.popleft() for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < N and 0 <= ny < M: if tmp_board[nx][ny] != 0: continue tmp_board[nx][ny] = 2 q.append((nx, ny)) for i in range(N): for j in range(M): if tmp_board[i][j] == 0: tmp += 1 return tmp if __name__ == '__main__': N, M = map(int, sys.stdin.readline().split()) board = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)] virus = [] ans = 0 for i in range(N): for j in range(M): if board[i][j] == 2: virus.append((i, j)) # 1번 벽 세우기 for x1 in range(N): for y1 in range(M): if board[x1][y1]: continue # 빈 공간이 아닐 경우 continue # 2번 벽 세우기 for x2 in range(N): for y2 in range(M): if board[x2][y2]: continue # 빈 공간이 아닐 경우 continue # 3번 벽 세우기 for x3 in range(N): for y3 in range(M): if board[x3][y3]: continue # 빈 공간이 아닐 경우 continue # 벽이 서로 다른 3가지가 될 수 있도록 같으면 continue if x1 == x2 and y1 == y2: continue if x2 == x3 and y2 == y3: continue if x1 == x3 and y1 == y3: continue # 벽 세우기 board[x1][y1] = 1 board[x2][y2] = 1 board[x3][y3] = 1 ans = max(ans, bfs(board, virus)) # 세웠던 벽 부수기 board[x1][y1] = 0 board[x2][y2] = 0 board[x3][y3] = 0 print(ans)
결과
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!
'Algorithm & Problem Solving > 그래프 이론(DFS & BFS)' 카테고리의 다른 글
[백준 1939] 중량제한 (Python) (0) 2021.01.27 [백준 2589] 보물섬 (Python) (0) 2021.01.25 [백준 11559] Puyo Puyo (Python) (0) 2021.01.22 [백준 16947] 서울 지하철 2호선 (Python) (0) 2021.01.20 [백준 14226] 이모티콘 (Python) (0) 2020.12.15