백준 문제 풀이 - 그래프 탐색
📰 문제
문제 확인 🏃
💡 입출력 예제
7
6
1 2
2 3
1 5
5 2
5 6
4 7
>> 4💬 풀이
🎵 첫번째 풀이
인접 행렬 + DFS
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
computer = [[0] * (N+1) for _ in range(N+1)]
visited = [0] * (N+1)
for _ in range(M):
i, j = map(int, input().split())
computer[i][j] = computer[j][i] = 1
def dfs(start):
visited[start] = 1
for i in range(1, N+1):
if not visited[i] and computer[start][i]:
dfs(i)
dfs(1)
print(visited.count(1) - 1)
🎵 두번째 풀이
인접 리스트 + DFS
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
computer = [[] for _ in range(N+1)]
visited = [0] * (N+1)
for _ in range(M):
i, j = map(int, input().split())
computer[i].append(j)
computer[j].append(i)
def dfs(start):
visited[start] = 1
for i in computer[start]:
if not visited[i]:
dfs(i)
dfs(1)
print(visited.count(1) - 1)
🎵 세번째 풀이
인접 행렬 + BFS
from collections import deque
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
computer = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
i, j = map(int, input().split())
computer[i][j] = computer[j][i] = 1
def bfs(start):
answer = 0
visited = [0] * (N+1)
queue = deque()
queue.append(start)
visited[start] = 1
while queue:
answer += 1
now = queue.popleft()
for i in range(N+1):
if not visited[i] and computer[now][i]:
queue.append(i)
visited[i] = 1
return answer - 1
print(bfs(1))
🎵 네번째 풀이
인접 행렬 + BFS
from collections import deque
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
computer = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
i, j = map(int, input().split())
computer[i][j] = computer[j][i] = 1
def bfs(start):
visited = [0] * (N+1)
queue = deque()
queue.append(start)
visited[start] = 1
while queue:
now = queue.popleft()
for i in range(N+1):
if not visited[i] and computer[now][i]:
queue.append(i)
visited[i] = 1
return visited.count(1) - 1
print(bfs(1))
🎵 다섯번째 풀이
인접 리스트 + BFS
from collections import deque
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
computer = [[] for _ in range(N+1)]
for _ in range(M):
i, j = map(int, input().split())
computer[i].append(j)
computer[j].append(i)
def bfs(start):
visited = [0] * (N+1)
queue = deque()
queue.append(start)
visited[start] = 1
while queue:
now = queue.popleft()
for i in computer[now]:
if not visited[i]:
queue.append(i)
visited[i] = 1
return visited.count(1) - 1
print(bfs(1))
✒️ 생각
할 수 있는 모든 방법은 해봤다...!😎
🐥 Backend Developer 🐥