dfs

[백준 2146번] 다리 만들기 - 파이썬

⚠️ 문제 - https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🔐 풀이 크게 두 단계로 나누어 문제를 풀었습니다. 1. 처음 주어진 지도에서 DFS를 사용해 각각의 섬을 다른 번호로 구분하기 2. 모든 섬에서 BFS를 사용해 다른 섬과의 최단 거리 구하기 (이 중 가장 작은 값이 정답) 🧑🏻‍💻 코드 import sys from collections import deque sys.setrecursionlimit(10**8) N = int(sys.st..

[Algorithm] DFS / BFS

대표적인 탐색 알고리즘인 DFS / BFS를 이해, 구현하기 위해 우선 스택과 큐 자료구조에 대해 간단히 알아보겠습니다.스택 - Stack스택은 박스를 쌓고 내리는 원리와 같습니다.먼저 들어온 것이 나중에 나가고 (FILO), 나중에 들어온 것이 먼저 나가는 (LIFO) 구조입니다.만약 1-3-5-7 순서로 들어왔다면, 7-5-3-1의 순서로 나가게 됩니다.파이썬에서는 별도의 라이브러리 사용없이 기본 리스트에서 append()와 pop() 메서드로 리스트를 스택처럼 사용할 수 있습니다.append() 메서드는 데이터를 리스트 가장 뒤쪽에 삽입하고, pop() 메서드는 데이터를 리스트의 가장 뒤쪽에서 꺼내기 때문입니다.큐 - Queue큐는 줄을 서는 원리와 같습니다.먼저 들어온 것이 먼저 나가고 (FIFO..