연구소
문제 0 - 빈칸, 1 - 벽, 2 - 바이러스일 때, 바이러스는 상하좌우로 0이 있으면 그 길을 통해 퍼진다. 이 때 벽을 3개 세워 바이러스를 막을 때, 바이러스가 아닌 부분의 최대 개수 (안전영역) 유형 분석 - 그래프와 연결된 모든 노드를 구해서 바이러스가 퍼지는 유형 -> DFS 벽을 세우는 경우의 수 : combinations 바이러스 처리 : DFS or BFS 코드 # 연구소 from itertools import combinations dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] def virus(x, y, test): for k in range(4): now_x = x + dx[k] now_y = y + dy[k] if now_x = n ..
미로탈출
문제 1 - 가능한 위치, 0 - 괴물일 때, (0, 0)에서 (n, m)까지 이동하는데 가장 짧은 거리 유형 파악 그래프가 주어지고 특정 노드의 위치를 탐색하는 것이므로 우선, BFS/DFS 이다. 코드 dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] from collections import deque def bfs(array, visited, start): visited[start[0]][start[1]] = True queue = deque() queue.append(start) while queue: x, y = queue.popleft() for i in range(4): next_x = x + dx[i] next_y = y + dy[i] if next_x < 0 or ne..
음료수 얼려먹기
문제 구멍 : 0, 칸막이 : 1 구멍이 뚫려있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결되어 아이스크림 생성 아이스크림의 수는? 유형 파악 우선 아이스크림을 만들려면 연결된 노드들을 파악하다가 더이상 연결된 노드들을 찾을 수 없을 때 아이스크림 하나가 생긴다. 따라서, 연결된 모든 노드들을 탐색할 수 있는 DFS/BFS를 사용할 수 있는데, 둘 다 사용이 가능하다. 코드 def dfs(array, visited, start): x = start[0] y = start[1] visited[x][y] = True dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] for i in range(4): next_x = x+dx[i] next_y = y+dy[i] if 0
