---

백준 1012 : 문제링크

• 문제유형 :

  • 그래프 탐색

  • DFS

• 설명

  • 연결 요소의 개수를 세는 문제
  • 모든 정점에 대하여 BFS를 수행하고, 한 번 방문한 정점은 다시 확인하지 않음
  • BFS를 수행한 총 횟수를 계산

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  import sys sys.setrecursionlimit(100000) def dfs(x, y): visited[x][y] = True directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dx, dy in directions: nx, ny = x + dx, y + dy if nx < 0 or nx >= n or ny < 0 or ny > m: continue if array[nx][ny] and not visited[nx][ny]: dfs(nx, ny) for _ in range(int(input())): m, n, k = map(int, input().split()) array = [[0] * m for _ in range(n)] visited = [[False] * m for _ in range(n)] for _ in range(k): y, x = map(int, input().split()) array[x][y] = 1 result = 0 for i in range(n): for j in range(m): if array[i][j] and not visited[i][j]: dfs(i, j) result += 1 print(result)

Comment and share

---

백준 2606 : 문제링크

• 문제유형 :

  • 그래프 탐색

  • DFS

• 설명

  • 시작 정점에서부터 도달할 수 있는 노드의 수를 계산

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  n = int(input()) m = int(input()) adj = [[] for _ in range(n + 1)] visited = [False] * (n + 1) count = 0 for _ in range(m): x, y = map(int, input().split()) adj[x].append(y) adj[y].append(X) def dfs(now_pos): global count count += 1 visited[now_pos] = True for next_pos in adj[now_pos]: if not visited[next_pos]: dfs(next_pos) dfs(1) print(count - 1)

Comment and share