백준 17835번 면접보는 승범이네
면접장들을 거리 0으로 잇는 가상 정점에서 역방향 다익스트라 한 번 돌리기, long long 필요
모든 태그
주제
#graph
글 58개
-
-
그래프 최단경로 알고리즘 정리
다익스트라, 벨만 포드, 플로이드 워셜의 사용 조건과 시간 복잡도, 음의 간선과 반복문 순서 같은 주의점
-
백준 23741번 야바위 게임
정점에 홀수 번 이동해 왔는지 짝수 번 이동해 왔는지만 구분해 반복 이동을 압축하는 BFS
-
백준 25953번 템포럴 그래프
시각 T마다 간선 완화를 한 번만 하도록 시각별 dist 배열을 따로 두는 벨만 포드 변형
-
백준 9370번 미확인 도착지
s-g-h-e 경로 길이가 s-e 최단 거리와 같은지로 특정 간선을 지나는 목적지만 거르기
-
백준 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
최단 거리가 갱신될 때 이전 노드를 기록해 목적지까지의 경로를 복원하는 다익스트라
-
백준 24526번 전화 돌리기
그래프를 뒤집고 진입 차수가 0인 노드를 지워 나가 사이클에 닿지 않는 노드 세기
-
백준 11097번 도시 계획
SCC마다 사이클 하나를 만들고 SCC 사이를 잇되, 다른 경로로 대신할 수 있는 간선은 빼고 출력하기
-
백준 2152번 여행 계획 세우기
SCC로 압축한 그래프에서 시작점에서 닿는 컴포넌트만 따라가며 방문 도시 수 최대화하기
-
백준 3977번 축구 전술
SCC를 구해 진입 차수가 0인 SCC가 하나뿐일 때만 그 안의 노드를 시작 전술로 출력하기
-
백준 4013번 ATM
SCC로 압축한 DAG에서 시작 SCC에서 닿는 경로만 따라가며 최대 현금을 구하는 DP
-
백준 6543번 그래프의 싱크
SCC로 압축한 그래프에서 나가는 간선이 없는 컴포넌트의 노드를 모두 출력하기
-
백준 1199번 오일러 회로
모든 정점의 차수가 짝수인지 확인하고 Hierholzer 알고리즘으로 간선을 한 번씩 쓰는 회로 만들기
-
백준 1948번 임계경로
위상 정렬로 최장 도착 시간을 구한 뒤 역방향으로 따라가며 임계 경로 간선 세기
-
백준 2637번 장난감 조립
위상 정렬 순서로 중간 부품의 기본 부품 필요량을 곱해 누적하기, 역추적으로 난 메모리 초과
-
백준 2848번 알고스팟어
이웃한 단어의 첫 차이로 알파벳 순서 간선을 만들고 위상 정렬로 모순과 여러 답 판정하기
-
백준 3665번 최종 순위
기존 순위로 모든 쌍에 방향 간선을 만들고 바뀐 쌍만 뒤집어 위상 정렬로 최종 순위 구하기
-
백준 1005번 ACM Craft
건물 선행 관계를 위상 정렬로 풀어 목표 건물의 최소 완성 시간 구하기, 전역 배열 초기화 실수까지
-
백준 1516번 게임 개발
위상 정렬 순서대로 선행 건물 완료 시간 중 가장 늦은 값에 자기 건설 시간을 더하기
-
백준 1766번 문제집
진입 차수가 0인 문제를 최소 힙에 넣어 번호가 작은 문제부터 푸는 위상 정렬
-
백준 2623번 음악프로그램
DFS 후 역순으로 출력하는 위상 정렬과 방문 중 상태로 사이클 찾기
-
백준 1647번 도시 분할 계획
MST를 만들다 간선이 N-2개가 되면 멈춰 가장 비싼 간선을 빼고 마을을 둘로 나누기
-
백준 1944번 복제 로봇
시작점과 열쇠 사이 최단 거리를 BFS로 구해 간선으로 만들고 MST로 모두 잇기
-
백준 2887번 행성 터널
x, y, z 좌표별로 정렬해 이웃한 행성 사이 간선만 후보로 두는 MST
-
백준 4343번 Arctic Network
위성 채널 수만큼 연결을 건너뛰고 MST에서 마지막으로 고른 간선 비용을 답으로 내기
-
백준 9373번 복도 뚫기
양쪽 벽과 센서를 정점으로 짧은 간격부터 이어 두 벽이 연결되는 순간의 거리 찾기
-
백준 5719번 거의 최단 경로
다익스트라 후 도착점부터 역추적해 모든 최단 경로 간선을 지우고 다시 다익스트라 돌리기
-
백준 14868번 문명
BFS로 문명을 넓히며 맞닿은 문명을 유니온 파인드로 합쳐 모두 이어지는 해 찾기
-
백준 3197번 백조의 호수
녹는 물을 BFS로 퍼뜨리며 이어진 물을 유니온 파인드로 묶어 백조가 만나는 날 찾기
-
백준 1600번 말이 되고픈 원숭이
말처럼 뛴 횟수를 BFS 상태에 넣어 벽 부수고 이동하기처럼 푸는 격자 최단 거리
-
백준 14442번 벽 부수고 이동하기 2
지금까지 부순 벽의 수를 BFS 상태에 넣어 K번 이하로 부수는 최단 거리 구하기
-
백준 16933번 벽 부수고 이동하기 3
낮과 밤, 부순 벽 수, 기다린 횟수를 BFS 상태로 기록해 밤에는 벽 앞에서 기다리는 최단 경로
-
백준 9328번 열쇠
열쇠 상태가 바뀌면 막혔던 칸과 테두리를 다시 탐색하는 BFS, visited 초깃값을 -1로 두는 이유
-
백준 1194번 달이 차오른다, 가자.
가진 열쇠를 비트마스크로 기록해 같은 칸이라도 열쇠 상태가 다르면 다시 방문하는 BFS
-
백준 2001번 보석 줍기
가진 보석 상태를 비트마스크로 두고 같은 섬, 같은 상태의 재방문을 막는 탐색
-
백준 1987번 알파벳
이미 쓴 알파벳을 기록하며 상하좌우로 가는 DFS 백트래킹으로 가장 긴 경로 찾기
-
백준 17071번 숨바꼭질 5
수빈이가 짝수·홀수 초에 도달하는 시간을 따로 기록해 움직이는 동생과 만나는 순간 판정하기
-
백준 1525번 퍼즐
퍼즐 상태를 문자열로 바꿔 map에 이동 횟수를 저장하는 BFS로 정답 상태까지의 최단 이동 찾기
-
백준 11967번 불켜기
불은 켜졌지만 아직 못 가는 방을 따로 기억했다가 길이 열리면 BFS에 넣기, 시작 방 불 켜기 주의
-
백준 16920 확장 게임
플레이어마다 큐를 따로 두고 각자 확장 거리만큼 번갈아 BFS를 돌려 점령 칸 세기
-
백준 4179번 불!
불이 번지는 시간을 먼저 BFS로 구하고 그보다 먼저 닿는 칸으로만 지훈이를 옮기기, 불이 없는 경우 주의
-
백준 5014번 스타트링크
건물 범위를 벗어나지 않게 위아래 층으로 BFS 해서 최소 버튼 횟수 구하기
-
백준 9466번 텀 프로젝트
선택 그래프를 DFS로 따라가며 사이클을 이루는 학생만 팀으로 세고 나머지 인원 구하기
-
백준 3482번 Labyrinth
칸 사이 경로가 하나뿐인 미궁을 트리로 보고 두 번의 BFS로 가장 먼 두 칸 사이 거리 구하기
-
백준 1167번 트리의 지름
아무 노드에서 가장 먼 노드를 찾고 거기서 다시 가장 먼 거리를 재는 두 번의 DFS가 맞는 이유
-
백준 12851번 숨바꼭질 2
같은 최단 시간으로 도착하는 경우도 큐에 넣어 최단 시간과 방법의 수를 함께 구하는 BFS
-
백준 13549번 숨바꼭질 3
비용 0인 순간이동을 먼저 처리하는 최단 경로, 우선순위 큐 대신 0-1 BFS로도 가능
-
백준 13913번 숨바꼭질 4
BFS로 최단 시간을 구하며 직전 위치를 함께 저장하고 도착점에서 경로를 거꾸로 따라가기
-
백준 2206번 벽 부수고 이동하기
벽을 부쉈는지 여부를 BFS 상태에 넣어 한 번만 부수고 가는 최단 경로 찾기
-
백준 11725번 트리의 부모 찾기
루트 1번에서 DFS 한 번으로 모든 노드의 부모를 함께 기록하기, 노드마다 탐색해 시간 초과가 난 첫 시도
-
백준 10026번 적록색약
같은 색 영역을 BFS로 세고, R을 G로 바꾼 격자에서 한 번 더 세는 적록색약 시야 처리
-
백준 2178번 미로 탐색
한 칸씩 이동하며 거리를 1씩 더하는 기본 BFS 최단 경로
-
백준 1012번 유기농 배추
이어진 배추 영역을 연결 요소로 보고 DFS가 새 영역을 찾을 때마다 지렁이 수 세기
-
백준 7576번 토마토
처음 익은 토마토를 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 날 구하기
-
백준 11724번 연결 요소의 개수
방문하지 않은 노드에서 탐색을 시작할 때마다 하나씩 세는 연결 요소, Python 재귀 깊이 제한 풀기
-
백준 2606번 바이러스
1번 컴퓨터와 연결된 노드를 DFS나 BFS로 세는 기본 그래프 탐색
-
백준 1697번 숨바꼭질
-1, +1, ×2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록하기
-
백준 1260번 DFS와 BFS
재귀로 짠 DFS와 deque로 짠 BFS, 작은 번호부터 방문하는 순서 처리