겜돌이의 개발일지

문제 백준 11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 1. 각각의 칸을 bfs로 탐색하여 없어지는 칸들을 구합니다. 2-1. 없어지는 칸이 없다면 더 이상 연쇄가 일어나지 않는 것이므로 루프를 종료하고 combo를 출력합니다. 2-2. 없어지는 칸이 있다면 그 칸들을 .으로 바꿔줍니다. 3. 그 후 아래칸부터 접근해 해당칸이 .이고, 그 윗칸이 .이 아닐 경우 당겨줍니다. (중력 적용) 4-1. 당겨지는 칸이 있을 경우에는 3번 과정으로 돌아가 계속 해서 당겨줍니다..

문제 백준 16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제 풀이 자체는 직관적인데 구현에 시간이 좀 걸렸습니다. 먼저 먹이를 bfs로 찾아줍니다. (먹이는 상어 크기보다 작아야 하고 상어 크기보다 큰 물고기는 지나갈 수 없습니다!!) 먹을 수 있는 먹이가 있으면, 상어가 이동하는 거리를 계산해 dtarr 배열에 넘깁니다. bfs가 끝나고 먹을 수 있는 먹이가 없으면, 종료하고 cnt를 출력합니다. 먹이가 있다면 가장 짧은 거리, 거리도 같다면 왼쪽 위에 있는 먹이를 목표로 설정합니다..

문제 백준 15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 리프 노드는 자식이 없으므로 서브 트리의 정점 개수는 자기 자신 1개입니다. 따라서 dp 배열을 1로 초기화해줍니다. 루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다. 부모가 -1인 경우는 루트 노드이므로 더하지 않습니다. 예제를 보겠습니다. 숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서..

문제 백준 2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 먼저 탑의 높이와 인덱스를 받는 stack을 선언합니다. 탑의 높이를 입력해주고, 뒤에서 부터 다음 과정을 실행합니다. 1. 스택이 비었을 경우에는 탑의 높이와 인덱스를 스택에 push 합니다. 2. 스택이 비어있지 않을 때는, 스택의 top과 현재 탑의 높이를 비교하여, top이 작다면 레이저가 도달한 것이므로 레이저가 닿는 탑의 위치를 저장하는 배열 receive에 탑의 위치를 저장해준 후, stack을 pop 합니다. 3. 계속해..

문제 백준 1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전형적인 트리 - dfs 문제입니다. 부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다. 이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다. 그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다. 리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다. 또한 제거된 노드 하나만을 자식으..

문제 백준 3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 처음에는 석순과 종유석을 입력받을 때 일일이 배열을 돌며 장애물을 계산해줬는데 당연하게도 시간 초과가 났습니다. (시간 복잡도가 N*H입니다) 따라서 누적합을 통해 시간 초과를 극복하고자 하였습니다. 먼저 석순과 종유석의 높이를 입력값으로 받습니다. (N은 항상 짝수이므로 석순과 종유석이 무조건 번갈아 나옵니다.) 높이를 각각의 배열에 체크해 둡니다. 그 후 루프를 돌며 높이마다의 석순과 종유석 개수를 누적합으로 구합니다. 예를 들어 석순의..

문제 백준 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 bfs와 dp를 섞은 듯한 재밌는 문제였습니다. q는 순서대로 현재 파이프 끝의 x좌표 / y좌표 / 상태를 저장합니다. q에다가 push와 pop을 반복하면서, 갈 수 있는 경로의 수를 파악합니다. 각각의 상태에 대해 취할 수 있는 다음 상태를 하드 코딩 했는데, 따로 함수를 만들었다면 더욱 깔끔한 코드가 되었을 것 같습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

문제 백준 14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 처음에 모든 블록을 하드 코딩하려다가 뭔가 잘못된 것을 깨닫고 풀이를 참조했습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양을 제외한 테트로미노는 시작 지점을 깊이가 0이라고 했을 때, 깊이가 3인 dfs로 표현할 수 있습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양은 하드 코딩(elseshape)으로 따로 점검해줍니다. map을 돌면서 해당 지점에서 만들 수 있는 테트로미노의 최댓값을 저장하고, maxsum을 넘는다면 maxsum을 바꿔줍니다. 모든 map을 다..

문제 백준 11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 n = 3일때 까지의 예시입니다. 첫번째 열은 1로 초기화를 해줍니다. 두번째 열은 길이가 1인 오르막 수 입니다. 1~9까지 10개가 있습니다. 세번째 열은 길이가 2인 오르막 수 입니다. 예를 들어서, 9x에 들어갈 수 있는 x는 9 1개 입니다. (누적 : 1개) 8x에 들어갈 수 있는 x는 8, 9 2개 입니다. (누적 : 3개) 7x에 들어갈 수 있는 x는 7, 8, 9 3개 입니다. (누적 ..

문제 백준 17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 투포인터를 사용합니다. 앞과 뒤에서 인덱스를 조절하며 팰린드롬인지 검사합니다. 만약 팰린드롬이 아니라면, check를 true로 바꿔주고 유사회문인지 검사하기 위하여 isPalin함수를 재귀호출합니다. 검사 후에, isP가 true고 check가 false면 팰린드롬, isP가 true고 check가 true면 유사회문, isP가 false인 경우에는 회문이 아니므로 각각에 맞는 정답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..