본문 바로가기

ALGORITHM

 (212)
백준 2589 보물섬 (Java) 1. 문제 링크 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 최단 거리 중 가장 먼 거리를 찾는 것이다. (뭔가 말이 이상하지만) bfs로 나온 거리들 중 가장 돌아서 가는 경우를 찾으면 된다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; pub..
백준 1309 동물원 (Java) 1. 문제 링크 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 조금 잘 생각해야 하는 dp문제였다. dp[i-1]에 사자가 왼쪽, 오른쪽 있다는 생각으로 dp[i-1]*2에 dp[i-2]를 더했다. 나머지 연산을 한 상태로 dp에 저장해야 한다. 점화식: dp[i] = (dp[i-1]*2 + dp[i-2]) % 9901 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) t..
백준 1715 카드 정렬하기 (Java) 1. 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A와 B를 합치려면 A+B번 비교해야 한다. 2. 작은 숫자 2개를 뽑아서 합치는 과정을 반복하면 된다. 3. PriorityQueue를 이용해서 2개를 뽑고 합을 다시 넣어서 다른 비교에 사용하도록 했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue..
백준 3055 탈출 (Java) 1. 문제 링크 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 고슴도치는 물이 찰 예정인 곳으로 갈 수 없기 때문에 먼저 물을 채우는 방향으로 진행했다. 물을 채우고 bfs 탐색을 하면 고슴도치가 갈 수 있는 곳을 큐에 넣는다. 큐가 비었는데도 도착하지 못했다면 KAKTUS를 출력한다. 4. 코드 import java.awt.List; import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..
백준 1600 말이 되고픈 원숭이 (Java) 1. 문제 링크 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 bfs로 탐색하는 문제이다. K번까지 움직일 수 있다고 정해져있기 때문에 좌표에 도착했을 때 몇번째로 도착했는지까지 생각해서 visit을 3차원 배열로 했다. 말의 움직임을 따랐을 때 움직임의 횟수를 증가하고, 원숭이의 움직임인 4방탐색의 경우에는 움직임의 횟수를 그대로 둔 상태로 이동한다. 4. 코드 import java.io.BufferedReader; import java.io.Inp..
백준 14499 주사위 굴리기 (Java) 1. 문제 링크 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 주사위 6면을 한 번에 다루면서 숫자를 옮겼다. 주사위가 떨어지는 1 2 3 4 방향에 따라 주사위 6면 전부를 움직였다. 주사위 배열은 상단, 하단, 동, 서, 남, 북 순으로 조작했다. 입력받은 명령에 따라 주사위에서 바꾸는 4부분의 값의 바꿨다. 도착한 바닥이 0이면 바닥에 주사위 하단의 숫자를 바닥에 넣는다. 도착한 바닥이 숫자라면 주..
백준 1012 유기농 배추 (Java) 1. 문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 배추가 나오면 bfs를 시작해서 인접한 배추를 전부 방문처리한다. bfs를 한 번 할 때마다 배추의 개수를 증가한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; public class Main..
백준 1331 나이트 투어 (Java) 1. 문제 링크 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 나이트의 이동 범위인지 확인하는 과정이 필요하다. 전에 있던 좌표와 x축 절댓값 차이가 2이면서 y축 절댓값 차이가 1인 경우거나 x축 절댓값 차이가 1이면서 y축 절댓값 차이가 2인 경우인지 판단한다. 또한 방문했던 좌표인지 확인하는 과정도 필요하다. 그 과정에서 flag가 바뀌었는지 판단해서 "Valid" 또는 "Invalid"를 출력한다. 4. 코드 import java.io.BufferedReader;..

티스토리툴바