깊이 우선 탐색(DFS; Depth-First search) 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 재귀 함수로 구현 스택 자료구조 이용 시간 복잡도(노드 수: V, 에지수: E) $O(V + E)$ 풀 수 있는 문제: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 방문 리스트 초기화하기 시작 노드 스택에 append()로 삽입하기 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 pop()으로 노드 꺼내기 꺼낸 노드를 탐색 순서에 기입 인접 리스트의 인접 노드를 스택에 삽..
BFS
트리의 지름 트리의 지름이라는 것은 1967번 문제에도 나와 있듯이 어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말하는 것이다. 즉, 아래 그림의 9번, 12번 노드 사이의 거리는 45로 어떤 두 노드보다 가장 긴 거리를 가지므로, 이 두 노드 사이의 거리가 주어진 트리의 지름이다. 따라서 우리가 이 문제에서 구해야 하는 것은 두 노드 사이의 최대 길이이다. 백준 1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 두 노드 사이의 최대 거리를..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 from collections import deque def solution(maps): n, m = len(maps), len(maps[0]) queue = deque() queue.append((0, 0)) # 시작 위치 큐에 추가 # 상하좌우 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # BFS while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] # nx, ny가 maps 범..
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline m, n = map(int, input().split()) # 가로, 세로 graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) # 익은 토마토의 위치 queue에 추가 queue = deque() for i in range(n): for ..
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제에서 연결 요소의 개수를 구하라고 했지만, 연결 요소의 뜻을 몰라서 헤매고 있었다. 하지만 주어진 예제 입력을 직접 손으로 그려보니 연결 요소가 무엇인지 알 수 있었다! 1번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다. 125 / 34 형태로, 2개의 그래프이자 2개의 영역으로 나눠진 것으로 볼 수 있다. 2번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으..
24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 코드 import sys from collections import deque sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 정점 graph = [[] for _ in range(n+1)] visited = [0] * (n+1) # 방문..