박카스러버

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 저는 우선순위 큐를 이용해 문제를 해결하였습니다. 저는 회사와 집의 입력을 먼 곳을 기준으로 같다면 가까운 곳을 기준으로 오름차순 정렬하였습니다. 이후 입력을 돌면서 가까운 곳이 먼곳 - 길이보다 큰 것은 우선순위 큐에 넣었습니다. 그리고 우선순위 큐의 앞 값이 현재 먼 곳 - 길이보다 작다면 계속 우선순위 큐에서 빼주고 각각의 입력에 대해 우선..

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를 통해 문제를 해결하였습니다. 저는 처음 입력 받을 때, 입력이 0이면 0을 넣고, 나머지는 -1을 넣었습니다. (도달 못 할 시 -1로 되도록 하기위해 이렇게 하였습니다.) 시작지점부터 BFS를 하여 각 지점의 최단 거리를 구하였습니다. package BOJ.bfs; import java.io.BufferedReader; import ja..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 저는 BFS를 통해 해당 문제를 해결하였습니다. P점부터 시작하여 BFS를 해 벽쪽으로는 진행하지 않고 빈 공간과 친구쪽은 BFS를 진행하도록 하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Linke..

https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 저는 크루스칼과 BFS를 통해 문제를 해결하였습니다. 크루스칼을 통해 최단 비용의 모든 마을을 연결하였고, 연결하면서 해당 edge를 저장하였습니다. 그리고 각각의 마을에서 BFS를 통해 가장 멀리있는 마을의 비용을 구하였습니다. package BOJ.mst; import java.io.BufferedReader; import java.io.InputStreamReader; import java..

https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 저는 해당 문제를 DP를 통해 해결하였습니다. DP를 통해 해당 숫자일 때 최선을 다했을 때 이길 수 있는지 없는지를 저장하였습니다. result에 넣을 때 이전 값의 음수를 넣는 이유는 내가 돌을 가져가면 상대방 차례로 돌아가기 때문에 전의 결과의 반대로 해주어야 합니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeniz..

https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 저는 dfs를 통해 문제를 해결하였습니다. dfs를 통해 각각 선택하고 visited로 해당 요소가 지워졌는지를 표시하였습니다. 이전과 다음은 visited아 아닌것이 나올 때까지 증가 감소 시켜 인덱스를 찾았습니다. package BOJ.dfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 방문 체크를 하고 해당 노드에 방문한 적이 없으면 방문하면서 결과값을 늘렸습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Q..

https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 저는 BFS를 통해 해당 문제를 해결하였습니다. BFS를 통해 각각의 노드를 방문하도록하고 도착점에 도달하면 도착하는 문구를 리턴하도록 하였습니다. visited를 안 사용하게 된다면 메모리 초과가 나오게 됩니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Linked..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 저는 DFS를 통해 해당 문제를 해결하였습니다. 저는 visited배열을 숫자로 저장하였습니다. 현재 숫자와 같은지 다른지 즉, 같은 사이클에 있는지 아닌지에 따라 다르게 처리하였습니다. 같은 숫자 즉, 같은 사이클이라면 true를 리턴하여 이때 결과값(SAFE_ZONE)의 개수를 늘렸습니다. 다르다면 false를 리턴하여 이때는 결과값을 늘리지 않았습니다. p..