Practice makes perfect!

- 문제 링크 : https://www.acmicpc.net/problem/2606 - 접근 방법 : 1번 컴퓨터에 연결된 모든 컴퓨터를 찾으면 되는 문제이므로 dfs로 접근. ( 현재 나의 위치에서 연결된 브랜치를 모두 방문하고자 할 때 ) n = int(input()) con = int(input()) graph = [[] for _ in range(n+1)] visited = [0]*(n+1) for _ in range(con): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) cnt = -1 def dfs(a): visited[a] = 1 global cnt cnt += 1 for b in graph[a]: if vis..

- 문제 링크 : https://www.acmicpc.net/problem/2178 - 접근 방법 : 처음엔 이동에 제약이 있는 경우라고 생각해 DFS로 풀었다. 예제 입력은 다 맞았지만 DFS는 모든 노드를 다 탐색하기 때문에 시간이 오래 걸려 런타임 에러가 떴다. 다시 문제를 읽어보니 '지나는 최소 칸 수' 즉 최단거리를 구하는 문제였다. 최단거리는 BFS로 접근해야하고, 인접한 경로의 거리를 업데이트하는 식으로 코드를 작성하였다. # DFS 사용, 런타임 에러 발생 n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] visited = [[0] * m for _ in range(n)] visited[0..

문제 링크 : https://www.acmicpc.net/problem/1303 접근 방법 : 인접한 병사들의 수를 세는 것이 목적이다. 현재 위치에서 모든 노드를 탐색할 필요없이 인접한 우리 병사의 수만 세면 되므로 BFS를 사용하였다. from collections import deque m, n = map(int, input().split()) graph = [list(input()) for _ in range(n)] dx = [1,-1,0,0] dy = [0,0,1,-1] W, B = 0, 0 visited = [[0]*m for _ in range(n)] q = deque() def bfs(x,y): q.append((x,y)) visited[x][y] = 1 cnt = 1 while q: x,..

► BFS (Breadth-First Search) - 너비 우선 탐색 - 현재 나의 위치에서 가장 가까운 노드들을 모두 방문 - 방문하면서 현재위치 pop, 방문할 곳 append, 방문한 곳 check ☞ 미로탐색 중 최단 거리를 찾는 문제, 임의의 경로를 찾는 문제에서 사용 ex) 우리나라에서 직통도로로 연결된 지역 중, 서울과 경기도 사이에 존재하는 경로를 찾고싶을 때 깊이 우선 탐색의 경우(DFS) - 전국의 모든 도로를 다 살펴봐야할 수도 있다. 너비 우선 탐색의 경우(BFS) - 서울과 인접한 도로먼저 탐색 from collections import deque visited = [False] * 10 def bfs(v): q = deque([v]) visited[v] = True while ..