Posts tagged "graph"

• 백준 17835번 면접보는 승범이네

  2023년 11월 24일 · #ps #boj #graph

  백준 17835번 면접보는 승범이네 풀이. 가상 정점에서 면접장들을 0거리로 연결해 역방향 다익스트라 한 번으로 각 도시의 최단 거리를 구한다.
• 그래프 최단경로 알고리즘 정리

  2023년 7월 2일 · #ps #graph

  그래프 최단경로 알고리즘 정리. 다익스트라, 벨만 포드, 플로이드 워셜의 사용 조건과 시간복잡도, 구현 포인트를 비교한다.
• 백준 23741번 야바위 게임

  2023년 7월 2일 · #boj #ps #graph

  백준 23741번 야바위 게임 풀이. 정점에 홀수 번 또는 짝수 번 이동해 도착했는지만 구분해 여러 번 간선을 타는 상태를 압축한다.
• 백준 25953번 템포럴 그래프

  2023년 7월 2일 · #boj #ps #graph

  백준 25953번 템포럴 그래프 풀이. 시간 T마다 가능한 간선 완화를 한 번씩만 적용하도록 시간별 dist 배열을 분리해 관리한다.
• 백준 9370번 미확인 도착지

  2023년 7월 2일 · #boj #ps #graph

  백준 9370번 미확인 도착지 풀이. 다익스트라로 특정 간선을 지나는 최단 경로가 존재하는 후보 목적지만 걸러낸다.
• 백준 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

  2023년 7월 2일 · #boj #ps #graph

  백준 9694번 풀이. 최단거리 갱신 시 이전 노드를 함께 저장해 목적지까지의 최단 경로를 복원한다.
• 백준 24526번 전화 돌리기

  2022년 3월 1일 · #graph #cpp #ps

  백준 24526번 전화 돌리기 풀이. 그래프를 뒤집고 진입 차수 기반 위상 제거를 수행해 사이클에 연결되지 않는 노드 수를 구한다.
• 백준 11097번 도시 계획

  2022년 2월 13일 · #cpp #floyd #ps #graph

  백준 11097번 도시 계획 풀이. SCC 내부 순환 간선과 SCC 간 필요한 간선을 구성해 조건을 만족하는 도시 계획을 출력한다.
• 백준 2152번 여행 계획 세우기

  2022년 2월 13일 · #dp #graph #cpp #ps

  백준 2152번 여행 계획 세우기 풀이. SCC를 압축하고 시작점에서 도달 가능한 컴포넌트만 따라가며 방문 가능한 도시 수의 최댓값을 구한다.
• 백준 3977번 축구 전술

  2022년 2월 11일 · #cpp #ps #graph

  백준 3977번 축구 전술 풀이. SCC를 구한 뒤 진입 차수가 0인 SCC가 하나뿐인지 확인해 가능한 시작 전술 노드를 출력한다.
• 백준 4013번 ATM

  2022년 2월 11일 · #dp #graph #cpp #ps

  백준 4013번 ATM 풀이. SCC를 압축해 DAG를 만들고 시작 SCC에서 도달 가능한 경로의 최대 수금액을 DP로 계산한다.
• 백준 6543번 그래프의 싱크

  2022년 2월 11일 · #cpp #ps #graph

  백준 6543번 그래프의 싱크 풀이. SCC 압축 그래프에서 나가는 간선이 없는 컴포넌트의 모든 원래 노드를 찾아 출력한다.
• 백준 1199번 오일러 회로

  2022년 2월 8일 · #graph #cpp #ps

  백준 1199번 오일러 회로 풀이. 모든 정점의 차수가 짝수인지 확인하고 Hierholzer 알고리즘으로 간선을 한 번씩 쓰는 회로를 만든다.
• 백준 1948번 임계경로

  2022년 2월 7일 · #graph #cpp #ps

  백준 1948번 임계경로 풀이. 위상 정렬로 최장 시간을 구한 뒤 역방향으로 추적해 임계 경로에 포함되는 간선 수를 센다.
• 백준 2637번 장난감 조립

  2022년 2월 4일 · #dp #graph #cpp #ps

  백준 2637번 장난감 조립 풀이. 위상 정렬로 중간 부품의 기본 부품 필요량을 누적해 완제품에 필요한 기본 부품 개수를 구한다.
• 백준 2848번 알고스팟어

  2022년 2월 4일 · #graph #cpp #ps

  백준 2848번 알고스팟어 풀이. 인접한 단어의 첫 차이로 알파벳 순서 그래프를 만들고 위상 정렬로 모순과 다중 해를 판정한다.
• 백준 3665번 최종 순위

  2022년 2월 4일 · #graph #cpp #ps

  백준 3665번 최종 순위 풀이. 기존 순위의 상대적 방향 간선을 만들고 바뀐 쌍을 뒤집어 위상 정렬로 최종 순위를 구한다.
• 백준 1005번 ACM Craft

  2022년 2월 3일 · #graph #cpp #ps

  백준 1005번 ACM Craft 풀이. 건물 선행 관계를 위상 정렬로 처리하고 목표 건물까지 필요한 최소 완성 시간을 계산한다.
• 백준 1516번 게임 개발

  2022년 2월 3일 · #graph #cpp #ps

  백준 1516번 게임 개발 풀이. 위상 정렬 순서대로 각 건물의 선행 건물 완료 시간 중 최댓값을 반영해 완성 시간을 구한다.
• 백준 1766번 문제집

  2022년 2월 3일 · #graph #cpp #ps

  백준 1766번 문제집 풀이. 진입 차수가 0인 문제를 최소 힙에 넣어 가능한 문제 중 번호가 작은 것부터 푸는 순서를 만든다.
• 백준 2623번 음악프로그램

  2022년 2월 2일 · #graph #cpp #ps

  백준 2623번 음악프로그램 풀이. DFS 기반 위상 정렬과 진행 중 방문 상태를 이용해 가능한 순서와 사이클 여부를 판단한다.
• 백준 1647번 도시 분할 계획

  2022년 2월 1일 · #graph #cpp #ps

  백준 1647번 도시 분할 계획 풀이. MST를 만들되 가장 큰 간선을 제외해 두 마을로 나누는 최소 유지비를 구한다.
• 백준 1944번 복제 로봇

  2022년 2월 1일 · #graph #cpp #ps

  백준 1944번 복제 로봇 풀이. 시작점과 열쇠 사이 최단거리를 BFS로 간선화하고 MST를 만들어 모든 열쇠를 연결한다.
• 백준 2887번 행성 터널

  2022년 2월 1일 · #graph #sort #cpp #ps

  백준 2887번 행성 터널 풀이. x, y, z 좌표별 인접 행성 간선만 후보로 삼아 MST 간선 수를 크게 줄인다.
• 백준 4343번 Arctic Network

  2022년 2월 1일 · #graph #cpp #ps

  백준 4343번 Arctic Network 풀이. 위성 채널 수만큼 네트워크를 분리하도록 MST에서 필요한 마지막 간선 비용을 계산한다.
• 백준 9373번 복도 뚫기

  2022년 2월 1일 · #graph #cpp #ps

  백준 9373번 복도 뚫기 풀이. 센서와 양쪽 벽을 정점으로 보고 MST처럼 연결해 두 벽이 막히는 최소 간격을 찾는다.
• 백준 5719번 거의 최단 경로

  2022년 1월 18일 · #graph #cpp #dijkstra #ps

  백준 5719번 거의 최단 경로 풀이. 모든 최단 경로에 포함된 간선을 역추적으로 제거한 뒤 다시 다익스트라를 수행한다.
• 백준 14868번 문명

  2021년 11월 25일 · #graph #union-find #cpp #ps

  백준 14868번 문명 풀이. BFS로 문명을 확장하고 인접한 문명을 유니온 파인드로 합치며 모두 연결되는 해를 찾는다.
• 백준 3197번 백조의 호수

  2021년 11월 25일 · #graph #union-find #cpp #ps

  백준 3197번 백조의 호수 풀이. 물 확산을 BFS로 진행하고 녹아 연결된 영역을 유니온 파인드로 묶어 백조가 만나는 날을 구한다.
• 백준 1600번 말이 되고픈 원숭이

  2021년 11월 12일 · #graph #cpp #ps

  백준 1600번 말이 되고픈 원숭이 풀이. 말처럼 점프한 횟수를 BFS 상태에 포함해 장애물이 있는 격자에서 최단 이동을 구한다.
• 백준 14442번 벽 부수고 이동하기 2

  2021년 11월 10일 · #graph #cpp #ps

  백준 14442번 벽 부수고 이동하기 2 풀이. 현재까지 부순 벽의 개수를 BFS 상태로 포함해 K번 이하로 벽을 부수는 최단 거리를 찾는다.
• 백준 16933번 벽 부수고 이동하기 3

  2021년 11월 10일 · #graph #cpp #ps

  백준 16933번 벽 부수고 이동하기 3 풀이. 낮과 밤, 벽을 부순 횟수, 대기 횟수를 상태로 기록해 조건이 있는 최단 경로를 탐색한다.
• 백준 9328번 열쇠

  2021년 11월 10일 · #graph #bitmasking #cpp #ps #simulation

  백준 9328번 열쇠 풀이. 열쇠 보유 상태가 바뀌면 이전에 막혔던 위치도 다시 탐색할 수 있게 처리해 문서 개수를 센다.
• 백준 1194번 달이 차오른다, 가자.

  2021년 11월 9일 · #graph #bitmasking #cpp #ps

  백준 1194번 달이 차오른다, 가자 풀이. 열쇠 보유 상태를 비트마스크로 기록해 같은 위치라도 다른 열쇠 상태면 다시 탐색한다.
• 백준 2001번 보석 줍기

  2021년 11월 9일 · #graph #bitmasking #cpp #ps

  백준 2001번 보석 줍기 풀이. 보유 보석 집합을 비트마스크로 관리하며 같은 섬과 같은 보석 상태의 중복 방문을 막는다.
• 백준 1987번 알파벳

  2021년 10월 27일 · #backtracking #graph #cpp #ps

  백준 1987번 알파벳 풀이. 지금까지 사용한 알파벳을 기록하면서 상하좌우로 이동 가능한 경로의 최대 길이를 DFS로 찾는다.
• 백준 17071번 숨바꼭질 5

  2021년 10월 26일 · #graph #cpp #ps

  백준 17071번 숨바꼭질 5 풀이. 수빈이의 도달 시간을 홀짝 상태로 나누어 기록하고, 움직이는 동생과 만날 수 있는 시점을 판정한다.
• 백준 1525번 퍼즐

  2021년 10월 24일 · #graph #hash #string #cpp #ps

  백준 1525번 퍼즐 풀이. 퍼즐 상태를 문자열 키로 표현하고 map에 이동 횟수를 저장하며 BFS로 목표 상태까지의 최단 이동을 찾는다.
• 백준 11967번 불켜기

  2021년 10월 23일 · #graph #cpp #ps

  백준 11967번 불켜기 풀이. 불은 켜졌지만 아직 갈 수 없는 방을 따로 기록하고, 새로 접근 가능해지는 방을 BFS에 반영한다.
• 백준 16920 확장 게임

  2021년 10월 23일 · #graph #cpp #ps

  백준 16920번 확장 게임 풀이. 플레이어별 큐를 따로 두고 각자의 확장 거리만큼 차례대로 BFS를 진행해 점령 칸 수를 계산한다.
• 백준 4179번 불!

  2021년 10월 19일 · #graph #cpp #ps

  백준 4179번 불! 풀이. 불의 확산 시간과 지훈이의 이동 시간을 따로 BFS로 구해 불보다 먼저 도달 가능한 탈출 경로를 찾는다.
• 백준 5014번 스타트링크

  2021년 10월 19일 · #graph #cpp #ps

  백준 5014번 스타트링크 풀이. 엘리베이터가 갈 수 있는 층을 BFS로 탐색하며 범위와 방문 시간을 관리해 최소 버튼 횟수를 구한다.
• 백준 9466번 텀 프로젝트

  2021년 10월 19일 · #graph #cpp #ps

  백준 9466번 텀 프로젝트 풀이. 학생 선택 그래프에서 사이클을 이루는 학생만 팀으로 분류하고 나머지 인원을 계산한다.
• 백준 3482번 Labyrinth

  2021년 10월 7일 · #graph #ps #python #tree

  백준 3482번 Labyrinth 풀이. 미궁을 트리처럼 보고 두 번의 BFS로 가장 멀리 떨어진 두 칸 사이의 거리를 구한다.
• 백준 1167번 트리의 지름

  2021년 10월 5일 · #graph #ps #python #tree

  백준 1167번 트리의 지름 풀이. 임의의 노드에서 가장 먼 노드를 찾고, 그 노드에서 다시 가장 먼 거리까지 탐색하는 두 번의 DFS를 설명한다.
• 백준 12851번 숨바꼭질 2

  2021년 9월 29일 · #graph #ps #python

  백준 12851번 숨바꼭질 2 풀이. BFS에서 같은 최단 시간으로 도달하는 경우도 큐에 반영해 최단 시간과 경우의 수를 함께 구한다.
• 백준 13549번 숨바꼭질 3

  2021년 9월 29일 · #graph #ps #python

  백준 13549번 숨바꼭질 3 풀이. 순간이동 비용이 0인 조건을 우선 처리하기 위해 우선순위 큐 기반 최단 경로 탐색을 사용한다.
• 백준 13913번 숨바꼭질 4

  2021년 9월 29일 · #graph #ps #python

  백준 13913번 숨바꼭질 4 풀이. BFS로 최단 시간을 구하면서 이전 위치를 함께 저장하고, 도착점에서 경로를 역추적한다.
• 백준 2206번 벽 부수고 이동하기

  2021년 9월 23일 · #graph #ps #python

  백준 2206번 벽 부수고 이동하기 풀이. 벽을 부쉈는지 여부를 BFS 상태에 포함해 한 번만 벽을 부수는 최단 경로를 탐색한다.
• 백준 11725번 트리의 부모 찾기

  2021년 9월 15일 · #graph #ps #python

  백준 11725번 트리의 부모 찾기 풀이. 루트 1번에서 한 번의 DFS를 수행하며 각 노드의 부모를 동시에 기록한다.
• 백준 10026번 적록색약

  2021년 9월 7일 · #graph #ps #python

  백준 10026번 적록색약 풀이. 일반 시야와 적록색약 시야를 각각 BFS로 탐색해 색 영역의 개수를 비교한다.
• 백준 2178번 미로 탐색

  2021년 9월 6일 · #graph #ps #python

  백준 2178번 미로 탐색 풀이. BFS로 한 칸씩 이동하며 방문 칸에 거리 값을 누적해 최단 경로 길이를 계산한다.
• 백준 1012번 유기농 배추

  2021년 7월 11일 · #graph #ps #python

  백준 1012번 유기농 배추 풀이. 배추가 이어진 영역을 그래프의 연결 요소로 보고, 새 영역을 발견할 때마다 필요한 지렁이 수를 센다.
• 백준 7576번 토마토

  2021년 7월 9일 · #graph #ps #python

  백준 7576번 토마토 풀이. 처음 익은 토마토들을 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 최소 시간을 계산한다.
• 백준 11724번 연결 요소의 개수

  2021년 7월 8일 · #graph #ps #python

  백준 11724번 연결 요소의 개수 풀이. 방문하지 않은 노드에서 탐색을 시작할 때마다 연결 요소 하나를 세는 DFS/BFS 방식을 정리한다.
• 백준 2606번 바이러스

  2021년 5월 25일 · #graph #ps #python

  백준 2606번 바이러스 풀이. 1번 컴퓨터와 연결된 노드를 DFS/BFS로 탐색해 감염되는 컴퓨터 수를 계산한다.
• 백준 1697번 숨바꼭질

  2021년 5월 22일 · #graph #ps #python

  백준 1697번 숨바꼭질 풀이. 현재 위치에서 -1, +1, *2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록한다.
• 백준 1260번 DFS와 BFS

  2021년 5월 21일 · #graph #ps #python

  백준 1260번 DFS와 BFS 풀이. 재귀 기반 DFS와 deque 기반 BFS를 구현하고, 방문 순서를 조건에 맞게 처리하는 방법을 정리한다.