![]()
https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 📝문제 📝풀이 우선순위큐를 이용한 bfs 하는 문제이다. 우선시 되어야 하는 기준은 1. 쓰레기를 지나지 않는 것 2. 쓰레기 근처도 지나지 않는 것 그런데 2 번 조건을 처리하기 위해 처음 입력때 받은 g 를 list 안에 넣고 list를 순회하면서 map의 값이 '.' => 'm' 으로 바꾸고 bfs를 수행할 Queue 의 Comparator를 정해 주었다. 출발지..
![]()
https://www.acmicpc.net/problem/2980 2980번: 도로와 신호등 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔 www.acmicpc.net 📝문제 📝풀이 총 시간을 (빨간불+파란불) 로 % 연산을 하여 현재 신호등이 빨간불인지 파란불인지 구간을 파악해야한다 구간을 section 이라고 했을 때 빨간불 지속시간 보다 작으면 => 빨간불 구간 or => 파란불 구간 기다리는 시간을 더해주고 다음위치로 이동할 때 이동거리 만큼 총 시간에 더해주는 식으로 하면 된다 import static java.util.Arrays.*; import stat..
![]()
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 📝문제 📝풀이 주어진 메달의 갯수로 어떤 나라가 몇등 했는지 구하는 문제이다 Medal 클래스를 만들고 비교연산을 위해 Comparable 인터페이스를 implements 한다. 비교순위를 보장해주는 TreeMap 컬렉션을 사용하여 똑같은 점수가 있을 경우 해당 점수의 value 를 List 안에 추가하는 방식으로 입력을 받는다 그런 다음 TreeMap을 순회하면서 구할 나라..
![]()
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 📝문제 📝풀이 구슬을 이동시키다가 빨간색 구슬만 구멍에 빠지는 최소 move 카운트를 return 하는 문제이다 우선 최소 횟수는 좌표 BFS 특성상 먼저 끝내는 것이 최소 횟수 이므로 종결조건을 만족하기만 하면 return 1. 총 4방향 {아래, 위, 오른, 왼} 으로 움직이는데 벽인 '#' 기호를 만날 때 까지 움직인다 2. 파란색 구슬의 좌..
![]()
https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 📝 문제 📝 풀이 S 초 뒤에 해당 위치 (X,Y) 의 바이러스 상태를 return 하는 문제이다. 바이러스가 퍼지는 조건은 번호 순 대로 차례대로 퍼진다 따라서 순위를 보장해 주는 우선순위큐에 주어진 map 의 좌표를 다음과 같은 순서로 넣는다 1. 시간순 2. 번호순 BFS를 수행하면서 탐색 할 위치에 바이러스가 없다면 map 의 값을 갱신 만약 종결조건인 S 시..
![]()
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net [문제] [풀이] 이 문제에 접근하기 위해서 벨만-포드 알고리즘을 사용해야 한다. 최단거리 알고리즘인 다익스트라는 음의 가중치를 가지고 사이클이 있을 경우 무한순회를 하면 끝 없이 최단경로를 음의 무한대로 갱신 시킬 수 있기 때문 여기서 중요한점 => 아무 정점에서 시작해도 음의 사이클을 찾을 수 있다 이게 무슨말이냐면 평소에 다익스트라를 쓸 때 항상 쓰던 거리배열 Distance[정..
![]()
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net [문제] [풀이] Union-Find 를 이용하여 푸는 문제이다. 1. 파티들 갯수 만큼 순회 2. 파티의 멤버 중 진실을 아는 사람이 있으면 union 연산으로 집합에 포함 시킨 후 카운트 하나 증가 시키고 다시 1번의 과정으로 반복 import java.util.stream.*; import static java.util.Arrays.*; import static java.util.stream.Colle..
![]()
https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr [문제] [풀이] 특정 거리까지의 마을만 배달이 가능하기 때문에 모든 정점에 대해 거리의 합을 알아야 한다 하지만 출발지는 고정되어 있다. => 다익스트라 알고리즘 이용 각 정점에 대한 거리 배열을 Distance라고 하면 주어진 K 보다 낮은 값을 가진 마을의 개수를 카운트 하면 된다. import java.util.stream.*; ..
