1260번 - https://www.acmicpc.net/problem/1260
DFS와 BFS
접근 방법
- 인접행렬 방식으로 작성
- 처음 코드 작성 후 제출시 런타임에러(RecursionError)
--> DFS의 재귀함수가 너무 많이 돌아가 발생
- 코드 수정 후 틀린 부분 --> DFS의 노드에서 돌아갈 곳이 없을 때의 반복을 구현하지 않았다..
- 수정해서 통과 !
import copy
from collections import deque
def dfs(graph, v):
if graph[v][v] != -1:
print(v + 1, end=' ')
for i in range(len(graph)):
graph[i][v] = -1 # 방문했다
while True:
node = graph[v].index(1) if 1 in graph[v] else None# 방문하지 않은 연결된 노드 가져오기
if node is None:
return
graph[v][node] = -1 # 방문했다
dfs(graph, node)
return
def bfs(graph, firstV):
queue = deque([firstV])
graph[firstV][firstV] = -1
for i in range(len(graph)):
graph[i][firstV] = -1 # 방문했다
while queue:
v = queue.popleft()
print(v + 1, end=' ')
while True:
try:
node = graph[v].index(1) # 방문하지 않은 연결된 노드 가져오기
except:
break
if graph[node][node] != -1:
queue.append(node)
for i in range(len(graph)):
graph[i][node] = -1 # 방문했다
N, M, V = list(map(int, input().split()))
# 인접행렬로 그래프 표현 ( 연결X --> 0 / 연결O --> 1)
graph = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
edge1, edge2 = list(map(int, input().split()))
graph[edge1 - 1][edge2 - 1] = 1
graph[edge2 - 1][edge1 - 1] = 1
dfs(copy.deepcopy(graph), V - 1)
print()
bfs(copy.deepcopy(graph), V - 1)
2606번 - https://www.acmicpc.net/problem/2606
바이러스
접근 방법
- BFS로 작성
- 인접리스트 - 2차원 리스트로 작성
DFS로 작성하면 더 간결해보임(딕셔너리로도 구현 가능할 듯)
import copy
from collections import deque
def bfs(graph, visited, V=1 ):
cnt = -1
queue = deque([V])
visited[V] = True
while queue:
virus = queue.popleft()
cnt += 1
while len(graph[virus]):
nextvirus = graph[virus].pop()
if visited[nextvirus] is False:
queue.append(nextvirus)
visited[nextvirus] = True
return cnt
N = int(input())
M = int(input())
# 인접리스트로 그래프 표현 ( 0번째 인덱스 사용 X )
graph = [[] for _ in range(N + 1)]
for i in range(M):
edge1, edge2 = list(map(int, input().split()))
graph[edge1].append(edge2)
graph[edge2].append(edge1)
visited = [False] * (N+1)
print(bfs(graph, visited, 1))
코드 정리 : https://github.com/mingxoxo/Algorithm/tree/master/baekjoon
GitHub - mingxoxo/Algorithm: 알고리즘
알고리즘. Contribute to mingxoxo/Algorithm development by creating an account on GitHub.
github.com
'study > 알고리즘' 카테고리의 다른 글
[알고리즘 / Oracle] 프로그래머스 - 입양 시각 구하기(1) (3) | 2021.11.19 |
---|---|
[알고리즘] 구현 : 시뮬레이션과 완전 탐색 (0) | 2021.11.10 |
[알고리즘] DFS/BFS (4) | 2021.11.08 |
[알고리즘] 이진탐색 (0) | 2021.11.04 |
[알고리즘] 그리디(Greedy) 알고리즘 (0) | 2020.10.11 |