2606 바이러스, 14502 연구소 - DFS/BFS

1. 2606 바이러스

 

1.1. 문제유형

• 그래프, BFS, DFS

1.2. 자료구조

• Q (deque): BFS 구현을 위한 큐 자료구조
• node (int): Q에서 꺼낸 현재 노드(Vertex)
• next (int): node와 연결되어 있으며 다음에 방문할 노드(Vertex)
• graph (2d-list): 인접 리스트(Adjacency list)로 노드에 연결된 간선(edge) 정보 저장
• visited (1d-list): 방문 여부를 확인하는 리스트

1.3. 해결과정

1. ⭐1번 노드부터 BFS를 순회하며 방문한 장소는 True로 표시한다.
2. 방문이 끝난 후 True의 개수를 출력한다.
3. 이 때, 1번은 포함하지 않으므로 -1한 값을 출력한다.

1.4. 소스코드

from collections import deque

def BFS(start):
    Q=deque([start])
    visited[start]=True

    while Q:
        node = Q.popleft()
        for next in graph[node]:
            if not visited[next]:
                visited[next] = True
                Q.append(next)
    print(visited.count(True)-1)

n = int(input())
m = int(input())
graph = [[] for _ in range(n)]
visited = [False]*n

for _ in range(m):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

BFS(0)

2. 14502 연구소

 

 

2.1. 문제유형

• 그래프, BFS, DFS, 브루트포스

2.2. 자료구조

1. 함수는 크게 2가지이다.
   • BFS(a,b): BFS탐색으로 바이러스(a,b)를 전파시키는 함수
   • count_map(): 바이러스 전파 후 안전구역 좌표를 세는 함수
2. graph (2d-list): 초기 map 정보를 저장하는 2차원 리스트
3. tmp (2d-list): graph를 deepcopy한 임시 지도
4. virus (list): 바이러스 좌표를 저장하는 리스트
5. cases (list): 벽을 세울 모든 map 좌표를 저장하는 리스트
6. c (2d-list): cases 좌표 중 3개의 벽을 세울 수 있는 경우의 수를 저장한 리스트
7. flag (boolean): c에서 벽을 세울 수 없는 조합을 판별하는 변수
8. answer (int): 최대 안전구역의 수를 나타내는 변수

2.3. 해결과정

1. ⭐전체 맵 중, 3개의 벽을 세울 수 있는 조합을 구한다.
2. 경우의 수마다 벽을 세우고 바이러스를 전파시킨다.
3. 바이러스 전파 후 남은 안정거리를 카운트한다.
4. 카운트 한 값이 answer보다 더 크다면 answer에 저장한다.

2.4. 소스코드

from itertools import combinations
from collections import deque
import copy

def BFS(a, b):
    Q=deque([[a, b]])
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if not (0<=nx<n and 0<=ny<m):
                continue
            if tmp[nx][ny]==0:
                tmp[nx][ny]=2
                Q.append([nx, ny])
    return 0

def count_map():
    global answer
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==0:
                cnt += 1
    if answer < cnt:
        answer = cnt

n,m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
virus = []
answer = 0

for i in range(n):
    for j in range(m):
        if graph[i][j]==2:
            virus.append([i,j])
cases = []
for i in range(n):
    for j in range(m):
        cases.append((i, j))
c = combinations(cases, 3)

for walls in c:
    flag = False
    tmp = copy.deepcopy(graph)
    for x, y in walls:
        if tmp[x][y]==0:
            tmp[x][y]=1
        else:
            flag = True
            break
    if flag:
        continue
    else:
        for x, y in virus:
            BFS(x, y)
        count_map()
print(answer)