슈뢰딩거의 진돗개

2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 아이디어 숫자들을 정점으로 생각하면 뽑은 숫자들의 집합이 일치한다 => 사이클이 있다고 볼 수 있다. 사이클을 검출하는 방법 : DFS DFS를 돌다가 DFS가 아직 다 돌지않은 정점을 만나게 되면 사이클이 있다고 생각할 수 있다. (다만 방문여부와는 별개로 생각해줘야한다. 처음 방문하는 정점도 DFS를 다 돌진 않은 상태니까) DFS를 돌면서 자신이 이전에 방문한 정점을 저장해준다면 DFS가 다 안돈 정점부터 차례대로 자기 자신을 만날 때 까지 정..

https://www.acmicpc.net/problem/1739 1739번: 도로 정비하기 첫째 줄에 테스트 데이터의 개수 T(1≤T≤10)가 주어진다. 각 테스트 데이터의 첫째 줄에는 세 정수 N, M, K가 주어진다. 다음 K개의 줄에는 각 버스의 운행 정보를 나타내는 네 정수 A, B, C, D가 주어 www.acmicpc.net 한창 그래프 이론, 특히 2-SAT을 풀던 시절 난이도에 쫄지 않고 도전해서 생각보다 빠른 시간내 해결했던 문제입니다. 문제 조건을 보면 시장이 도로들에 방향성을 주어서 일방통행을 시키겠다고 합니다. 이말인 즉슨 (1) 도로는 (위, 아래) 또는 (왼쪽, 오른쪽)으로만 값을 가질 수 있음을 알 수 있고 도로의 혼잡을 줄이기 위하여 최대 2개의 도로만 이용하므로 (2) 목..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 전형적인 그래프 이론과 dp가 섞인 문제입니다. 파이프의 머리를 기준으로 위치를 잡아주면 (1,2)에서부터 (n,n)까지 이동하면 되는데 이때 파이프의 자세를 고려해줘야 합니다. 파이프가 가로로 누워있다면 45도밖에 못 움직이기에 가로로 평행이동하거나 대각선 아래로 이동하면서 오른쪽 아래 대각선이 될 것입니다. 이와 마찬가지로 세로인 경우도 제한 사항이 생기며 대각선인 경..