💻 첫째 줄 입력
n, m, v = map(int, sys.stdin.readline().split())
# 각 노드가 연결된 정보를 표현할, 2차원 리스트 생성
graph = [[0]*(n+1) for _ in range(n+1)]
visited = [False] * (n + 1) n = 4일 때, graph = [[0 0 0 0 0],[0 0 0 0 0],[0 0 0 0 0],[0 0 0 0 0],[0 0 0 0 0]]
visited = [False False False False False]
정점의 번호는 1번부터 N번까지인데, index가 0부터 시작하기 때문에 N+1을 해서 리스트 index를 4까지 만들었다. (index[0]를 비우기 위해서)
💻 둘째 줄 입력
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a][b] = graph[b][a] = 1
m개의 간선에 대해서, 간선으로 연결되는 두 정점의 번호들을 입력으로 받는다.
이때, 입력으로 주어지는 간선은 양방향이므로, graph[a][b] = graph[b][a] = 1를 쓴다. 이 부분은 이해가 잘 가지않아 구글링을 열심히 해봤다.
예를 들어, n=4일 경우 백준 1260의 예시에 따르면, graph = [[0 0 0 0 0],[0 0 1 1 1],[0 1 0 0 1],[0 1 0 0 1],[0 1 1 1 0]] 가 된다.
즉 정점1은 2,3,4과 연결되어 있고, 정점2은 1,4가, 정점3은 1,4, 정점4는 1,2,3과 연결되어 있다는 뜻이다.
[python 문법 tip]
반복문으로 여러줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 발생할 수 있습니다. 그래서 sys.stdin.readline() 사용
map은 a, b를 여러 개의 데이터를 한 번에 다른 형태로 변환하기 위해 사용하는 함수.
💻 DFS 선언
def dfs(v):
visited[v] = True
print(v, end=' ')
for i in range(1, n+1): # 그래프를 돌면서 방문을 안했으면, 재귀
if not visited[i] and graph[v][i] == 1:
dfs(i)v는 처음 시작하는 정점의 번호
False로 되어있는 visited[V]를 True로 바꾸는 이유는 나중에 V가 다시 중복되지 않기 위해서이다. (방문체크)
print안에 end=" "를 쓰는 이유는 출력값을 한 줄에 나란히 적어야하기 때문이다. end=" " 때문에 한칸씩 띄어지면서 다음 print되는 값이랑 한 줄에 같이 나온다.
숫자가 1부터 4까지이기 때문에 range(1, N+1)이다. 0은 안쓰기로 했으므로!
if not visited[i]는 visited[i]가 False이면 if를 충족한다. 동시에 graph[V][i]가 1이여야 한다. (왜? 1이여야 인접해있다는 뜻이므로!!)
그렇게 되었을 때 재귀함수를 사용해서 다른 숫자로 넘어간다.
💻 BFS 선언
def bfs(v):
# queue 구현을 위헤 deque 라이브러리 사용
queue = deque([v])
visited[v] = False #방문함
while queue:
v = queue.popleft()
print(v, end=" ")
for i in range(1, n+1):
if visited[i] and graph[v][i] == 1:
queue.append(i)
visited[i] = Falsevisited[V]를 위의 dfs()함수와 같이 사용하므로, dfs()에서는 방문했을 때 True였으니까, bfs()에서는 방문표시를 False로 한다.
dfs()와 마찬가지로, for문을 통해 아직 방문하지 않은 인접한 원소들을 큐에 삽입후 방문처리해준다. queue가 빌 때까지 while문을 실행
코드 보러 가기 👉1260.py
💻 마치면서..
코딩테스트를 보려면, DFS와 BFS를 무조건 잘 알아야한다~라는 말을 대학교 저학년때부터 들었던 것 같다. 잘 알지못하는 단어를 들으니 어려울 것 같다는 생각이 들었는데, 막상 해보니 재미있었다. 이번에 1260번 문제를 풀면서 각각의 개념이해를 더 잘 한 것 같다. 앞으로는 응용문제를 열심히 풀어봐야지😊
피드백은 언제나 환영입니다.💛
[참고사이트]
https://leedaeho1188.tistory.com/38 [Front-end Developer]
https://www.youtube.com/watch?v=7C9RgOcvkvo
