https://www.acmicpc.net/problem/4920 4920번: 테트리스 게임 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓 www.acmicpc.net 풀이 5가지 조각으로 배치할 수 있는 모든 도형의 경우의 수(총 13가지)를 배열로 지정하여 풀었다. 주의할 점 - n을 입력받을 때와 NxN 표를 입력받을 때 trim()을 해주어야 한다. - 표에 쓰이는 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다. 즉, 음수가 입력될 수 있으므로 초기 max값을 Integer.MIN_VALUE로 초기화한다. 코드 import java.i..

https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 풀이 처음 문제를 봤을 때는 BFS 알고리즘을 생각했다. 같은 위치를 다시 방문하면 안되기 때문에 boolean[] visited 방문 배열을 사용해야겠다고 생각했다. 하지만 단순한 방문배열이 아닌, 현재 탐색 단계와 이전 탐색 단계를 구분하는 방문 배열이 필요하다. ex) EEW W EW - 인덱스가 3인 W부터 시작해서 탐색할 때 왼쪽의 EEW와 합쳐진다. 따라서 카운트하지 않는다..

https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다. 또한 이미 탐색했던 상태가 나올 수 있으므로, Map map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다. 동전 상태는 다음과 같이 문자열로 저장된다. H T T H T T T H H -> HTTHTTTHH BFS 로직 1. 초기 동전상태를 큐와 Map에 추가한다..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 모든 정점에 대해 모든정점까지의 최단거리를 구해야 하기 때문에 그래프 최단거리 알고리즘을 사용했다. 1

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에 그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다. 다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해 Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다. static ..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 목표지점을 시작으로 하는 BFS를 수행하여, 각 지점까지의 최단거리를 구하면 된다. 주어진 지도는 map, 각 지점까지의 최단거리는 answerMap에 저장한다. 원래 갈 수 없는 위치는 0을 출력하고, 원래 갈 수 있는 땅 중에서 도달할 수 없는 위치는 -1을 출력하기 위해, answerMap을 모두 -1로 초기화한다음, map이 0인 위치는 0..

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 BFS를 사용해서 최소 이동 횟수를 구하면 된다. BFS를 수행할 때, checkWall() 메서드를 사용하여 직사각형이 이동할 위치에 벽이 있는지 체크한다. 주의할 점으로는, (1, 1)부터 시작하기 때문에 Sr, Sc, Fr, Fc를 저장할 때 -1을 해야 한다. 코드 import java.io.*; import java.util.*; public class Ma..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 BFS를 사용해서 출발지부터 목적지까지의 최단거리를 구하면 된다. 최단거리를 총 2번 구하는데, 검을 얻지 않는 상태와 검을 얻은 상태의 최단거리를 구하여 비교한다. 둘 중 더 작은 최단거리가 T보다 작거나 같다면 그 값을 출력하고, 그렇지 않다면 Fail을 출력한다. int bfs(int startR, int startC, int destR, int destC): (star..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 풀이 문제를 이해하기 위해 직접 격자판과 폭탄을 그려보았다. 이 때 폭탄이 설치된 위치에는 폭탄이 설치된 초를 써넣었다. 백준의 예시를 봐도 확인할 수 있다. 이를 보면 2초 후 부터는 폭탄 채우기와 폭탄 터뜨리기가 번갈아 수행되는 것을 알 수 있었다. 따라서 int형 2차원 배열을 선언하여 빈 칸은 -1, 폭탄이 있으면 해당 폭탄이 설치된 초를 저장하도록 하여 로직을 수행하도록 했다. 로직 1. 먼저 격자 상태를..

https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 풀이 1. 옵션이 입력될 때마다 아래의 로직대로 단축키를 찾는다. 1-1. split으로 단어들을 저장하여 각 단어의 첫글자가 단축키로 지정될 수 있는지 확인한다. 1-2. 2번에서 단축키를 구하지 못했다면 옵션에서 각 단어의 첫글자를 제외하고, 왼쪽에서 차례대로 글자들을 보면서 단축키가 가능한 글자를 찾는다. 1-3. 어떠한 것도 단축키로 지정할 수 없으면 옵션 그대로의 문자열을 ..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 BFS를 응용하여, 첫째 줄의 숫자를 고르면 그 숫자에 둘째 줄에 있는 숫자를 큐에 집어넣는 과정을 반복해서 최종적으로 각 숫자들이 2번씩 포함되는지를 체크하였다. 한 사이클을 찾아내면, 첫째 줄과 둘째 줄이 같은 숫자들을 추가하여 크기를 구하여 최대 크기의 사이클을 계속해서 업데이트하는 로직을 생각했다. 하지만 사이클이 여러 개 있을 수 있고, 각 숫자는 오직 1개 이하의 사이..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 PriorityQueue를 사용하여 풀었다. PriorityQueue를 선언할 때 조건에 맞는 Comparator 생성자를 사용하여 선언하면 된다. 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..