스톤헤드 부수기

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 난이도 : 골드 3 DFS와 메모이제이션을 이용했습니다. 메모이제이션은 다이나믹 프로그래밍처럼 이전에 계산해 둔 값을 나중에 계속 이용하여 불필요한 계산을 줄일 수 있습니다. 이 문제에서 숲의 최대 크기는 500x500입니다. 메모이제이션을 이용하여 계산의 중복을 막아 시간 초과를 예방했습니다. 판다가 이동할 4방향의 칸을 DFS를 통해 계산해줬습니다. 그리고 4방향 중 최댓값에서 1을 ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 난이도 : 골드 4 가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2 일 것입니다. 여기서 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있습니다. 가장 먼 노드는 dfs로 구했습니다. https://www.acmicpc.net/p..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도 : 골드 4 맵을 나눠 90도로 회전하는 것이 헷갈렸습니다. 종이에 적어가며 푸니 쉽게 이해가 됐네요. 정답을 구할 때 dfs를 이용하여 칸 수를 세주며 총얼음의 양을 구했습니다. 전역 변수 int n = 맵 크기의 지수(2^n) int size = 맵 크기 int map[][] = 문제에서 주어진 값 int dx[], dy[] = 좌표를 이동하기 위한 배열 int su..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 난이도 : 골드 3 매우 간단한 방법으로 풀었기 때문에 시간 복잡도 등은 최적화되지 않은 풀이입니다. 같은 섬은 DFS로 같은 번호로 묶었습니다. 그 후 모든 섬의 좌표에서 BFS로 다리를 만들었습니다. 이 경우 스택을 통해 모든 좌표를 저장했으며 큐, 리스트, 배열 등 아무 자료 구조를 사용해도 무방합니다. 전역 변수 int n = 입력받은 맵의 크기 int map[][], island[][] = 입..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 난이도 : 골드 4 우선 이 문제를 풀기 위해서는 이분 그래프에 대해 알아야 합니다. 저는 문제를 처음 읽었을 때 이분 그래프를 잘못 이해해서 이상한 방향으로 갔습니다. 이런식으로 그래프가 2덩어리로 나눠진 것을 찾는 문제인지 알았어요.. 하지만 이런 친구가 이분 그래프였습니다. 이분 그래프에 대해 쉽게 설명드리겠습니다. 전 어렵고 전문적이게 설명을 못 하기 때문이예요. 저는 이렇게 ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 난이도 : 골드 5 개인적으로 이런 유형의 문제를 좋아해서 재밌게 풀었습니다. 여러 기능을 구현하다 보면 열심히 일 하는 느낌(?)이 들어서 기분이 좋아요. 다양한 기능이 필요하지만 어렵지 않고 각 기능만 제대로 구현한다면 잘 동작하는 문제였습니다. 한 사이클에 터질 수 있는 블록을 모두 체크해두고 사이클이 끝나면 그 블록들을 터트린 후 위에 붕 떠있는 블록들을 밑으로 내려주는 과정을 반복하면 됩니다. 쉽죠? 전역 변수 map[][] = 게임판 answer = 몇 사이클 돌았나?(답..