121ms BFS 인접행렬 시작 index부터 방향 그래프로 연결된 index로 계속해서 가지처럼 뻗어나가며 마지막의 도달하는 index를 출력하는 문제이다. 마지막에 도달하는 index가 여러 개일 경우 가장 큰 index를 출력한다. 번호index와 도달하는 시간time을 저장할 수 있는 node 클래스를 만들어 BFS를 진행하며 큐가 비어 종료하기 직전 시간과 일치한 시간을 가진 node 중 index가 가장 큰 node를 출력하는 방식으로 구현하였다. 시작값start을 먼저 먼저 큐에 담고 방문처리한 후, 방향그래프인 graph[start][]와 연결된 i를 찾아 방문처리 및 시간을 하나 증가하여 큐에 넣어주며 가지가 끝날 때까지 반복해준다. 큐가 종료하기 직전에 저장한 lastTime과 일치하는..
129ms 구현 DFS 최대한 많은 코어를 전원에 연결할 경우, 필요한 전선 길이의 합의 최소를 구하는 문제이다. 단, 전선끼리 교차할 수 없다. (x,y) 좌표에서의 코어가 (x, 0), (x, n-1), (0, y), (n-1, y) 까지 전선을 설치할 수 있는지, 설치할 수 있는 경우에서 전선의 길이가 최소로 되는 방향으로 설치할 수 있도록 한다. 1. 가장자리가 아닌 코어들의 좌표를 리스트에 저장 2. 코어 리스트를 하나씩 돌며 상하좌우 탐색하며 전선을 설치할 수 있는 방향을 찾은 후 방문처리하며 DFS 탐색 진행 2-1. 방문처리하며 진행하다가 중간에 끊겨 해당 방향으로 전선을 설치할 수 없다면 코어의 좌표까지 다시 되돌아가며 방문처리 해제 3. 전선을 설치할 수 있는 방향이 있다면 전선 길이의..
구현 DFS 가장 높은 봉우리에서 시작하여 가장 긴 등산로를 찾아 길이를 출력하는 문제이다. 이 때, 딱 한 곳을 최대 K 깊이만큼 깎을 수 있다는 옵션이 있다. 가장 높은 봉우리 좌표에서 시작하여 상하좌우 탐색하며 처음으로 이전 봉우리보다 큰 봉우리를 만난 경우, 1 ~ K 깊이로 깎아 이전 봉우리보다 작아지면 이어서 탐색할 수 있도록 한다. 딱 한 곳만 깎을 수 있으므로 한 번 깎았다면 탐색 중 큰 봉우리를 만나도 지나갈 수 없다. 1. 이전 봉우리보다 낮으면 방문처리 후 재귀 2. 이전 봉우리보다 높으면서 한 곳 깎을 수 있는 경우 2-1. 이전 봉우리보다 낮아질 때 까지 깎기 ( 최대 K ) 2-2. 낮아지면 방문처리 및 깎는 공사를 한 번 진행했으므로 flag = true 3. 백트래킹 impo..
10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 92ms DFS BFS 적록색약일 경우의 나눠지는 구역과 적록색약이 아닐 경우 나눠지는 구역의 수를 세는 문제이다. 입력값을 저장할 이차원 배열을 두 개 선언하여 적록색약이 아닌 경우 입력값을 그대로 저장하고 적록색약인 경우에는 'G'값을 'R'값으로 저장하였다. 이중 for문을 돌며 적록색약이 아닌 경우의 dfs, 적록색약인 경우의 dfs 탐색을 통해 주변의 같은 색 좌표들을 모두 방문처리하여 구역을 카운팅하는 방식으로 구현하였다. 좌표의 상하좌우를 탐색..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 228ms DFS 치킨가게 중 M개를 선택할 때, 각 집의 치킨 거리 합의 최소값을 구하는 문제이다. 치킨가게의 좌표와 집의 좌표만 필요하므로 입력되는 값들을 이차원 배열에 저장하지 않아도 된다. 두 개의 List 를 선언하여 치킨가게 좌표와 집의 좌표를 따로 저장해주었다. 치킨가게를 포함하는가 포함하지 않는가의 문제로 DFS를 이용하였으며 치킨가게의 포함 여부를 판단하기 위해 boolean[] 배열을 추가로 선언해줬다. M개의 치킨가게를 선..
131ms BFS 구현 경우에 따라 가지처럼 뻗어나가는 구조로 BFS 를 이용하여 구현하였다. 탈주범의 위치와 시간을 저장할 수 있는 Node 클래스를 만들어서 맨홀의 위치(시작위치)를 Queue에 넣고 반복문을 시작해준다. 터널의 모양에 따라 갈 수 있는 방향인지, 영역 내인지, 방문한 곳인지 조건문을 통해 체크한 후 지나갈 수 있는 곳이라면 방문 체크 및 한 시간을 더하여 다시 큐에 넣어주며 반복한다. 지정한 시간이 되거나 더이상 이동할 경로가 없는 경우 = Queue가 빈 경우 반복문이 종료되며 탈주범이 있을 수 있는 위치를 count한 값을 출력해준다. 여러 조건만 잘 체크하면 쉽게 풀 수 있는 문제였다. 👩🏻💻 소스코드 import java.io.BufferedReader; import jav..
13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS 최소비용을 찾는 문제로 BFS로 해결할 수 있었다. 수빈이의 위치와 시간을 저장하는 Node 클래스를 생성한 후, 3가지 연산(*2, +1, -1)을 수행하며 K까지 도달했을 때 최소 시간을 저장해준다. N, K의 범위는 0 ~ 100,000 으로 *2와 +1 연산을 할 때, 100,000을 초과되지 않도록 주의하고, -1 연산을 할 때, 0 미만이 되지 않도록 주의해준다. 👩🏻💻 소스코드 import java.io...
11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 누적합 2차원 배열에 대해 누적합을 저장하는 경우 O(N*N)의 시간 복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어든다. prefixSum[a][b] 를 (1,1)부터 (a,b) 까지의 합이라고 하자 왼쪽이 주어진 배열이고 오른쪽이 누적합을 저장한 이차원 배열이다. (1,1)에서 (2,3)까지의 누적합을 구하고자 하면 왼쪽 누적합과 위쪽 누적합을 더한 값에 교집합으로 두 번 더해지는 구간을 한 번 빼준 후 (2..
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 알고리즘 이 문제는 DP를 대표하는 배낭 문제로 냅색 알고리즘(knapsack)로 풀이하는 문제이다. 배낭이 수용할 수 있는 최대 무게가 정해지고 배낭에 넣은 물건들의 가치의 최대합을 구하는 문제이다. 냅색 알고리즘은 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있다. Fraction Knapsack : 짐을 쪼갤 수 있는 배낭문제로 탐욕 알고리즘(greedy)로 풀이 0/1..
12907번: 동물원 동물원에 동물이 N마리 있고, 1번부터 N번가지 번호가 매겨져 있다. 이 동물원에 동물은 토끼나 고양이밖에 없고, 모든 동물의 키는 다 다르다. 수빈이는 토끼와 고양이를 구분할 수 없지만, 토끼 www.acmicpc.net 해당 문제는 동물들이 자신보다 키가 큰 고양이 or 토끼 수 를 말할 때, 각 대답이 어떤 동물이 했는지 가능한 경우의 수를 구하면 되는 문제이다. 이 문제의 핵심은 모든 동물의 키는 서로 다르다로 다음과 같은 특징을 알 수 있다. 1. 동물의 대답(입력값) 중 같은 값이 최대 2번 나올 수 있다. 예시) 자신보다 키가 큰 동물이 한 마리 있다고 토끼가 말한 경우와 고양이가 말한 경우로 최대 2번 2. 동물의 대답은 토끼 및 고양이 각각 연속된 수열로 이루어져 있..
1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 💡 DP (Top-Down) 오른쪽 방향 또는 아래 방향으로 탐색하며 도착지점까지 가는 경로의 개수를 찾는 문제로 처음은 DFS로 해결하였지만 시간초과로 인해 DP를 활용하여 특정 경로에서 도착지점까지 가는 경로 개수를 저장해두고 방문한 경로이면 저장한 경로 개수를 return하며 해결할 수 있었다. DFS로 구현했을 때 시간초과가 난다면 DP 로 해결하기 해당 좌표에서 도착지점까지 가는 경로의 개수가 0인 좌표와 처음 방문하는 좌표를 구분하기 위해 ..
12018번: Yonsei TOTO 첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어 www.acmicpc.net 💡 Priority Queue 가장 적은 마일리지로 가장 많은 과목을 수강하기 위해서는 모든 과목에 사용해야하는 최소의 마일리지를 구한 후, 가장 적게 드는 과목부터 주어진 마일리지를 초과하지 않도록 하나씩 더하면 풀 수 있는 문제이다. 1. 각 과목에 신청한 마일리지들을 높은 우선순위 큐에 넣어준다. 2. (수강인원-1)이 될 때까지 마일리지가 큰 순서대로 poll 해준다. 한 자리는 성준이자리 2-1. 신청한 사람 수보..
