https://www.acmicpc.net/problem/19236 문제 아기 상어가 성장해 청소년 상어가 되었다. ([그래프/시뮬레이션] 아기상어 백준 16236번) 4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에...
아기상어 백준 16236번 그래프 시뮬레이션
https://www.acmicpc.net/problem/16236 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2...
최종 순위 백준 3665번 그래프
https://www.acmicpc.net/problem/3665 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인...
행성터널 백준 2887번 그래프
https://www.acmicpc.net/problem/2887 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. ...
어두운 길 University of Ulm Local Contest 그래프
한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위...
탑승구 그래프
공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 탑승구 중 하나에 도킹을 해야 합니다. 이때 다른 비행기가 도킹하지 않는 탐승구에만 도킹 할 수 있습니다. 또한 P개의 비행기를 순서대로 도킹하다가 만약 어떤 탑승구에...
여행 계획 그래프
각 여행지는 1~N번 까지의 번호로 규정되어 있습니다. 두 여행지 사이에는 이동할 수 있는 도로가 있습니다. 그리고 도로는 양방향으로 이동이 가능합니다. 여행 계획을 세운 뒤에 이 여행 계획에 가능한지 여부를 판단하고자 합니다. 예시 5 4 (도시의 개수, 여행 계획하는 도시 수) 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 ...
그래프 이론 알고리즘 유형별 정리
코딩테스트에서 그래프 문제를 자주 만나볼 수 있습니다. 이때 간선간의 비용이 들기도 하고 아니기도 하고(그럴때는 모두 1) 가장 짧은 거리 가장 긴거리 특정한 조건을 만족하는 수(루트에서 리프까지 같을때 합이 얼마 인것의 개수는?) 되게 여러가지 변형 문제가 있습니다. 1. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합입니다. 집합 간의 ...