[백준] 2606번 - 바이러스 풀이 시간: 10분 이내 (풀이1) BFS 이용 이 문제는 노드 1이 포함된 그래프에서 1을 제외한 노드의 수를 구하는 문제다. 해당 문제는 입력받은 간선 정보를 통해 그래프(2차원 리스트)를 만들고 DFS/BFS로 문제를 풀 수 있다. 1) 문제 해결 아이디어 아래 코드는 BFS로 구현한 방법이다. 2) 소스코드 from collections import deque n = int(input()) # 컴퓨터 수 m = int(input()) # 컴퓨터 간선 수 graph = [[] for _ in range(n + 1)] visited = [False] * (n + 1) res = 0 # 1이 감염시킨 컴퓨터 수 for i in range(m): a, b = map(int..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
[이코테] 문제1 - 음료수 얼려 먹기 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이 문제는 DFS 혹은 BFS로 해결 가능하다. 특정 지점에서 DFS/BFS를 수행하여 이동 가능한 모든 지점에 대해 방문 처리를 한다. dfs 문제는 재귀 함수를 이용하여 해결한다. 재귀 함수의 종료 조건은 해당 좌표가 범위를 벗어났을 경우다. 현재 좌표를 아직 방문하지 않았다면 방문 처리를 하고 상하좌우에 해당하는 좌표를 매개변수로 하여 dfs를 호출한다. 1. 해당 지점이 아직 방문하지 않은 곳이라면 방문 처리 2. 상하좌우 지점 재귀 호출로 탐색 2) 소스코드 n, m = map(int, input().split()) # 세로, 가로 graph = [list(map(int, input())) for _ in ..
[이코테] BFS 예제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 BFS 예제 문제로 책 147p 참고 BFS 구현을 위해 큐(deque 라이브러리) 이용 2) 소스코드 from collections import deque # BFS 메서드 def bfs(graph, start, visited): # 큐 구현을 위한 deque 라이브러리 사용 queue = deque([start]) # 현재 노드 방문 처리 visited[start] = True # 큐가 빌 때가지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 for i in graph[v]: if..
