[Baekjoon] Baekjoon 1260 문제 풀이
Baekjoon 의 1260 문제를 풀었고, 해당 문제는 DFS, BFS 의 기초적인 문제이므로 추후에 DFS, BFS 의 코드적인 개념을 까먹었을 때 참고하기 위해 포스트로 정리해 보고자 합니다.
1. 문제 소개
Baekjoon 사이트의 정책상 문제의 저작권은 문제를 만든 사람에게 있다고 합니다. 그래도 블로그에 문제와 관련해서 링크로 넣는 것은 상관 없다고 하여 문제 내용은 링크로 대체하겠습니다. 자세한 문제 내용은 링크를 통해 사이트를 방문하여 확인해 주시길 바랍니다.
2. 문제 풀이
풀이 내용
제가 생각하는 이 문제를 풀기 위한 핵심은 다음과 같습니다.
- 입력으로 주어진 연결된 정점의 정보들을 인접 행렬 혹은 인접 리스트 방식으로 받아오기
- DFS 는 재귀 형식으로 구현, BFS 는 큐를 이용해 구현
- 인접한 정점을 방문할 시 작은 순서부터 방문하기 -> 정렬이 필요한데 어디서 정렬을 할 것인지
아마도 지금 이 글을 보고 계시는 분들은 제가 그랬듯 문제를 풀다가 도저히 못 풀겠어서 검색을 하다가 우연히 이 글을 찾게 되어 보고 있을거라고 생각합니다. 밑에 정답 코드가 있긴 하지만 우선 혹시 모르니 DFS 와 BFS 의 개념을 보고, 관련 코드를 확인한 후에 다시 한 번 자신이 직접 풀어 보시는 것을 추천 드립니다. 그런 의미에서 제가 정리한 기초적인 DFS 와 BFS 블로그 글이 있으니 DFS/BFS 정리를 보고 다시 한 번 본인이 직접 문제를 풀어보시기 바랍니다.
정답 코드
저는 연결된 정점 정보들을 인접 리스트 형식으로 받아 왔습니다. 그리고 문제의 핵심이 되는 정렬의 경우 DFS 는 파라미터로 받아오는 정점과 연결된 정보들을 하나씩 훑어 보기 전에 해주었고, BFS 는 queue 에서 꺼낸 정점과 연결된 정점들을 하나씩 훑어 보기 전에 정렬을 해주었습니다. 아니면 입력을 모두 받은 다음, 인접 리스트 각각을 사전에 미리 정렬을 해두는 것도 하나의 방법이 될 수 있을 것 같습니다.
import sys
from collections import deque
def solution(graph, start, vertex_num):
"""
:param graph: 연결된 정점들을 모아 놓은 리스트
:param start: 시작 정점
:param vertex_num: 정점의 개수
:return:
"""
# DFS 함수
def DFS(graph, visited, start):
"""
:param graph: 인접한 정점들을 모아놓은 리스트
:param visited: 방문한 정점을 체크하기 위한 리스트
:param start: 시작 정점
:return:
"""
print(start, end=" ") # 우선 파라미터에 있는 start 를 바로 출력
visited[start] = True # 방문한 정점을 체크하는 리스트에서 start 위치에 있는 정점을 방문 체크
graph[start].sort() # 문제에서 크기가 작은 정점부터 가라고 했으니 정렬 진행
for i in graph[start]: # start 정점과 인접한 정점들을 하나씩 가져옴
if not visited[i]: # 인접한 정점들이 방문 체크가 되어 있지 않으면
DFS(graph, visited, i) # DFS 함수 재귀 호출
def BFS(graph, visited, start):
"""
:param graph: 인접한 정점들을 모아놓은 리스트
:param visited: 방문한 정점을 체크하기 위한 리스트
:param start: 시작위치
:return:
"""
queue = deque([start]) # 시작위치 정점을 우선 큐에 넣어준다
visited[start] = True # 그리고 방문 리스트의 시작 위치에 방문 체크를 해준다
while queue:
v = queue.popleft() # 큐에서 popleft 를 해준다
print(v, end = " ") # 출력
graph[v].sort() # 작은 정점들부터 방문해야 하므로 정렬 진행
for i in graph[v]: # start 정점과 인접한 정점들을 하나씩 가져옴
if not visited[i]: # 인접한 정점들 중에서 방문 체크가 되어 있지 않은 정점이 있다면
queue.append(i) # 큐에 넣어줌
visited[i] = True # 방문 체크 진행
visited = [False] * (vertex_num+1) # 방문 체크 리스트 정의
DFS(graph, visited, start)
print()
visited = [False] * (vertex_num+1) # 방문 체크 리스트 정의 재정의
BFS(graph, visited, start)
input = sys.stdin.readline
n, m, start = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
solution(graph, start, n)
위 코드 제출 결과 맞았습니다!! 라고 정답인 것을 확인할 수 있었습니다.
마치며
Baekjoon 에서 DFS 와 BFS 의 기초적인 문제를 풀어보았습니다. 이번 문제는 단순히 DFS 와 BFS 의 개념만 알고 있어도 쉽게 풀 수 있는 문제였습니다. 하지만 요즘엔 이런 탐색 알고리즘들이 적용된 유용한 라이브러리들이 많아서 직접 구현할 일이 없어 저 같은 경우 시간이 지나면 까먹어 오랜만에 직접 구현을 해보려고 하면 버벅이는 경우가 더러 있었습니다. 그래서 그런 경우를 최대한 없애고자 이렇게 포스트로 정리해 보게 되었습니다.
긴 글 읽어주셔서 감사드리며, 이 글이 도움이 되셨으면 합니다. 그리고 내용 중에 잘못된 내용 혹은 오타, 궁금하신 사항이 있으시면 댓글 달아주시기 바랍니다.
Comments