https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 문제가 조금 복잡하기 쓰여있지만, 하얀 색으로 칠할 수 없고 모든 입력이 칠할 수 있는 경우로만 주어지므로 그렇게 어렵게 생각하지 않아도 될 듯 하다. 기본적인 트리 탐색 알고리즘인 dfs와 bfs 중 하나 골라서 풀어도 되는데, 필자는 bfs로 골랐다. 핵심은 바로 부모와 나(자식)의 색깔 차이이다. 부모와 색이 다르다면 무조건 색을 한번 칠해야 하므로 그럴 때 마다 카운트를 해주면 된..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프인지 아닌지를 판단하는 문제이다 정점 하나하나씩 bfs 탐색을 진행해주는데, 주의해야 할 점은 그룹을 지어야 한다는 것이다! (왜 bfs를 한번에 돌리지 않고, 정점 하나씩 해주냐면 입력이 어떻게 들어올 지 모르기 때문이다. 비연결 그래프가 존재하는 경우, 시작점과 연결되지 않은 곳은 탐색할 수 없기 때문에 모든 정점에 대해 탐색해주는 것이다) 트리를 하나 떠올려 보자. level 0 ..
https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 상당히 까다롭게 풀었던 문제인데, 파이썬 후기가 없어서 글을 남긴다. 우선 시루의 위치에서 시작하여 bfs를 돌리며 매번 마네킹에 근접했는지 검사하는 방식으로 하려 했으나, 당연히 시간초과 및 자잘한 오류들이 많이 생겼다.. 해결하기 위해선, 마네킹들의 위치에서 bfs를 돌려 마네킹에 근접한 곳들을 따로 체크해둔다. 배열을 ..
https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 조금 지저분하게 푼 것 양해바랍니다,, 우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다! 주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다. 사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에..
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 시리즈의 최종판이다. 이 문제는 다른 문제들과 달리, 동생의 위치에 포커싱을 맞춰야한다. (1초에는 1만큼 움직이고, 2초에는 2만큼 움직인다) (즉, 움직인 거리로 시간을 대체할 수 있다!) 만약 수빈이가 14초에 x라는 지점을 방문했다고 하자. 그런데 동생이 20초에 그 x지점을 방문했다. 그럼 수빈이와 동생은 20초만에 만날 수 있는 것이다. 라..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질1에 이은 문제이다. 숨바꼭질1은 최단경로를 찾아 루트부터 해당 노드까지의 거리(= 가장 빠른 시간)를 출력하고 바로 종료했다면, 이 문제는 큐가 빌 때 까지 모든 경우를 다 탐색해주면 된다. 물론, 가장 빠른 시간이 찾아지면 그보다 시간이 오래 걸리는 경로는 필요없으므로 트리가 한단계 더 깊어지면 멈춰준다. 이것은 약간의 트릭이다. 멈추지않고 찾아도 ..
