스톤헤드 부수기

난이도 : 골드 2 크루스칼 알고리즘을 이용하여 풀었습니다. 크루스칼 알고리즘을 이용하기 위해서는 간선의 정보가 필요합니다. 행성의 최대 개수는 10만 개가 들어옵니다. 행성 간의 모든 간선을 구하려면 대략 100,000^2의 시간 복잡도가 걸립니다. 시간초과를 예상할 수 있는 크기입니다. 굳이 모든 행성 간의 거리를 구할 필요는 없습니다. 현재 행성에서 가까운 행성간의 거리만 구하면 됩니다. 간선의 가중치는 x, y, z의 최소 값입니다. 즉, 어떤 행성의 최소 가중치의 간선은 x, y, z별로 정렬한 후 앞, 뒤의 값을 비교하여 구할 수 있습니다. 이해가 되지 않는다면 코드를 보며 이해하시길 바랍니다. 전역 변수 int n = 행성의 수 int parent[] = 그룹의 대표를 나타내는 배열 Plan..

난이도 : 골드 2 유니온 파인드 문제입니다. 하지만 입력은 숫자가 아닌 문자열이 주어집니다. map을 이용하여 각 이름(문자열)마다 숫자를 부여해줬습니다. 그리고 이 숫자를 기준으로 union-find를 했습니다. count는 초기 값을 모두 1로 갖습니다. n1, n2가 가지는 count 값을 union을 할 때 대표에게 값을 몰아줍니다. 그리고 이 값을 출력합니다. f번 다른 이름이 2개씩 들어올 수 있으므로 최대 배열 크기는 2*f로 했습니다. 전역 변수 int parent[] = 그룹의 대표를 나타내는 배열 int count[] = 친구의 수 함수 void main 입력을 받고 count와 parent 배열을 초기화해줍니다. f번 입력을 받으며 map에 이름이 없을 경우에 문자열 이름과 번호를 ..

난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다. 유니온은 도시들을 묶고 파인드는 이러한 도시의 대표를 찾습니다. 그룹의 대표를 그 그룹에서 가장 작은 값으로 정했습니다. 대표는 그룹마다 통일성을 가진다면 어떤 값으로 해도 상관은 없습니다. 단, 이 대표를 통하여 그룹을 구분할 수 있어야 합니다. 예를 들면 [1, 2, 3, 4, 7, 8], [5, 6], [9]의 그룹은 각 그룹의 대표를 1, 5, 9로 설정합니다. 각 그룹의 대표를 저장하는 parent배열을 위와 같이 나타내 볼 수 있습니다. 최적화를 위해 그룹의 대표를 건드릴 때는 find를 이용합니다. parent 절대 xx..

난이도 : 골드 3 다익스트라 알고리즘을 이용해 풀었습니다. 2020/11/02 - [문제풀이/자바] - [백준 1753] 최단경로 (자바) [백준 1753] 최단경로 (자바) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째.. jellyinghead.tistory.com 위 링크에 다익스트라 설명이 있습니다. 1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구했습니다. 그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했습니다. 그리고 이 두 값을 마을..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 난이도 : 골드 5 다익스트라 알고리즘을 이용해 풀었습니다. 다익스트라 알고리즘은 음의 가중치가 없을 때 최단 경로를 탐색할 수 있습니다. 그중 저는 우선순위 큐를 이용하여 풀었습니다. 아래의 그래프는 1에서 출발할 때의 가중치의 값입니다. 출발지 정점에서 연결된 정점의 가중치 값 입력 방문하지 않았고 가장 작은 가중치의 값을 가지고 있는 정점 방문 방문한 정점에서 연결..

https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 난이도 : 골드 3 테트리스와 비슷하게 구현하면 됩니다. 블록을 놓았을 때 파랑, 초록에 적절히 이동시키고 라인이 채워지면 점수 올리고 연한 부분 처리만 해주면 됩니다. 저는 오타 때문에 꽤 오랜 시간 헤맸네요. 복붙을 할 때에는 정신 바짝 차려서 해야겠습니다. 가독성을 잡기 위해 길이를 포기했기 때문에 디버깅이 쉽지 않네요. 전역 변수 int score = 총 점수 int blue[]..

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/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 난이도 : 골드 4 바람이 이동하는 것은 재귀를 이용하여 풀었습니다. 바람이 2번 꺾일 때마다 걸음 수가 1씩 증가하는 것을 규칙으로 움직입니다. 실수하지 않기 위해 wind 메소드의 길이가 매우 길어졌습니다. 가독성을 포기한다면 길이를 줄일 수 있겠네요. 칸마다 이동하며 좌표 값이 정상 범위를 벗어난다면 밖으로 떨어진 것이니 그때마다 out에 더해줬습니다. 전역 ..