백준 문제 풀이

문제 요구 사항 N x N 크기의 체스판에서, (r1, c1) → (r2 → c2) 로의 최소 이동 횟수를 출력한다. 해설 문제에서 주어지는 방향에 따라 BFS를 잘 구현하자. 일반적인 나이트의 움직임이 아니다. 코드

문제 요구 사항 N번째 칸토어 집합의 근사를 출력한다. 해설 일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다. 최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다. 따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다. 코드

N x N 크기의 지도가 주어진다. 0은 바다, 1은 육지를 나타낸다. 출력 한 대륙에서 다른 대륙으로 다리를 놓았을 때, 가장 짧은 다리의 길이를 출력한다. 해설 처음에 생각을 잘못 접근하면 이상한 길로 샐 수 있는 문제다. 단순하게 각 대륙에서 무수히 많은 사람이 동시에서 출발하고, 어딘가에서 만나걸라고 생각한다. 그리고 만난 사람들에 대해서, 지금까지 온 거리를 확인해보자. 말이 어려울 수 있다.. 코드로 보자. 코드

문제 요구 사항 입력 N x N의 땅이 주어진다. 각 칸에 몇 명이 사는지 주어진다. 인구 이동이 일어나는 조건 L, R이 주어진다. 출력 인접한 두 칸의 인구 차이가 L이상 R 이하인 경우, 인구 이동이 일어난다. 인구 이동이 며칠 동안 발생하는지 구해서 출력한다. 해설 문제 상에서 인구 이동을 하는 과정은 DFS든지, BFS든지 일단 구현할 수 있다. 단, 인구 이동이 잘 끝나는지 검사 해야 한다. 왜일까. 일단 인구이동의 조건 중, L이 0이상이다. 그 말은 모든 칸이 같은 인구 수가 되었어도 인구 이동이 일어난 것으로 생각할 수 있다. 따라서, 이 조건을 고려하여 정말 인구 이동이 일어난 건지 확인해야 한다. 코드