스택 구현 : append, pop
무방향 그래프의 인접행렬의 모양은?
-> 대칭적이다. = 전치가 의미가 없음
stack = [1] # 맨처음 시작점은 1번 포도알
visited = []
-----------------------------------------준비상태
while stack: # 스택이 빌때까지 돌아라!
current = stack.pop() # 우선 스택에서 현재 위치 하나 뽑고
if current not in visited: # 방문하지 않은 곳이라면,
visited.append(current) # 방문했다고 체크해줌
---------------------------------------------로직1
# 위의 if문 안으로 넣으면 더 좋습니다.
for destination in range(V+1): # current 입장에서 어디로 갈 수 있는지 모조리 체크
if adj_matrix[current][destination] and destination not in visited: # 갈수있고 + 방문 안했으면!
stack.append(destination) # 다음 갈 곳으로 Stack에 저장
---------------------------------------------로직2
<dfs 깊이우선탐색 준비>
stack이 빌 때까지 회차 반복
<1회차>
로직 1)
stack.pop() => 1
-> cur = 1 (현재 위치 = 1)
-> 현재 cur가 visited에 없으면 방문체크 하기. visited.append(1)
로직 2)
아직 가지 않은 곳이면서(not in visited) and 현재 cur와 이어져있는 곳(길이 있음) 탐색
-> 그것을 stack에 넣음
-> 회차 종료
1), 2) 로직을 노드만 바꿔가며 계속 반복 -> 재귀함수로도 가능
파이썬이기 때문에 스택에 중복값 쌓여도 상관 없음.
-> 스택에 기존 노드보다 많은 수가 쌓일 수 있음.
루프를 다 돌아도 스택이 빌 때까지 돌아야 함.
visited가 찍힌 후 스택들은 다 pop됨
<준비>
<1회차>
7 8 # Vertex = 7개, Edge = 8개인 그래프가 있을 때, (무조건 트리 아님)
1 2 # 다음 8개의 줄에 연결 정보를 제공
1 3 # 누구랑 누구가 연결되어있는지임.
2 4
2 5
4 6
5 6
6 7
3 7
a = [[0]*3]*3
a[0][0] = 9
a
[[9, 0, 0], [9, 0, 0], [9, 0, 0]]
b = [[0]*3 for _ in range(3)]
b[0][0] = 5
b
[[5, 0, 0], [0, 0, 0], [0, 0, 0]]
- 인접 행렬 : 공간은 더 잡아먹지만 탐색이 빠름, 전치 등 확장성이 좋다
- 인접 리스트 : 공간은 덜 잡아먹지만 시간은 더 걸림, 유의미한 결과값에선 평균적으로 더 빠르다
V, E = map(int, input().split()) # Vertex(포도알), Edge(선) 갯수
adj_matrix = [[0] * (V + 1) for _ in range(V + 1)] # 인접행렬 기본틀 + 0번 포도알은 안씀
for _ in range(E): # 간선 갯수만큼 돌면서 연결 정보를 받음
start, end = map(int, input().split()) # 시작점과 끝점
adj_matrix[start][end] = 1
adj_matrix[end][start] = 1 # 양방향 그래프니까!!
# adj_matrix print 결과
# [[0, 0, 0, 0, 0, 0, 0, 0], => 0번 포도알은 존재하지 않음
# [0, 0, 1, 1, 0, 0, 0, 0], => 1번 포도알은 2, 3번으로 갈 수 있음
# [0, 1, 0, 0, 1, 1, 0, 0], => 2번 포도알은 1, 4, 5번 가능
# [0, 1, 0, 0, 0, 0, 0, 1], => 3번 포도알은 1, 7번 가능
# [0, 0, 1, 0, 0, 0, 1, 0], => 4번 포도알은 2, 6번 가능
# [0, 0, 1, 0, 0, 0, 1, 0], => 5번 포도알은 2, 6번 가능
# [0, 0, 0, 0, 1, 1, 0, 1], => 6번 포도알은 4, 5, 7번 가능
# [0, 0, 0, 1, 0, 0, 1, 0]] => 7번 포도알은 3, 6번 가능
양방향 그래프
무방향 그래프의 표현
V, E = map(int, input().split())
adj_list = [[] for _ in range(V + 1)]
for _ in range(E):
start, end = map(int, input().split())
adj_list[start].append(end)
adj_list[end].append(start) # 양방향
# adj_list = [[], [2, 3], [1, 4, 5], [1, 7], [2, 6], [2, 6], [4, 5, 7], [6, 3]]