스톤헤드 부수기

난이도 : 골드 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/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에 더해줬습니다. 전역 ..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치� www.acmicpc.net 난이도 : 골드 5 LinkedList 2차원 배열을 이용하여 풀었습니다. 1차원 배열만 이용해봤는데 2차원 배열은 처음으로 써봤습니다. 매 턴이 되면 불들이 이동을 할 텐데 불들이 이동할 때 동시에 이동해야 합니다. 이 부분을 적절히 처리하지 않는다면 오동작을 합니다. 저는 새로운 배열을 만들어서 불을 하나씩 이동시킨 후 이 배열을 참조하도록 했습니다. ..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부�� www.acmicpc.net 난이도 : 실버 1 문제 이해를 못해서 지문을 몇 번 읽었는지 모르겠습니다. 제가 헷갈렸던 부분을 위주로 설명하겠습니다. 이 그림을 처음에 컨베이어 벨트를 위에서 바라본 모습으로 착각했네요. 이런 형식의 그림으로 착각해서 시작부터 꼬였습니다. 이런 식으로 컨베이어 벨트를 옆에서 바라본 것으로 생각하면 이해하기 쉽습니다. 위 그림의 경우 1~5가 상단에 위치하고 있고 1이 ..

https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 � www.acmicpc.net 난이도 : 플레 1 할 수 있을 것 같아 시작한 구현 문제인데, 할 수는 있었는데 좀 복잡했습니다. 어려운 것은 없었고, 문제를 천천히 읽으며 모든 조건을 만족하도록 버그를 잡는 것이 힘들었습니다. 맞다고 생각하며 작성한 코드에서 그렇게 많은 버그가 있을 줄은 몰랐습니다. 좀 더 필기를 꼼꼼히 하고 생각을 정리하며 문제를 풀어야겠습니다. 기회가 된다면 자바가 가진 객체 지향..

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