백준 | 1238번. 파티 - 다익스트라 문풀
⬛ 백준 1238번. 파티 - 다익스트라 문풀 다익스트라 : one - to - All : 한 정점에서 다른 든 정점에 대한 최단거리 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 31.
백준 |1167번. 트리의 지름 - BFS 응용 문제
⬛ 백준 1167번. 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 30.
백준 | 7576번. 토마토 - BFS 응용
⬛ 백준 7576번. 토마토 | BFS - 출발점이 여러 개인 BFS를 어떤 식으로 처리할지 고민해야 한다. 하나의 큐에 출발점 담아두고 while()문으로 순회하면서 BFS 레벨 탐색을 한다. 이 문제에서 레벨 == 최소일자가 된다. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 30.
백준 | 18126번. 너구리 구구 - DFS, BFS 풀이
⬛ 백준 18126번. 너구리 구구 - DFS, BFS 풀이 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net [주의] long 타입으로 변수를 선언해야 정답이 맞다. 길 하나의 길이가 10억이고, 방은 최대 5,000개까지 존재하므로 특정 방까지의 이동 거리는 최대 5^12까지이므로 long 타입을 사용해야 한다. 문제 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 29.
백준 | 1865번. 웜홀 - 벨만포드
⬛ 백준 1865번. 웜홀 - 벨만포드 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 25.
백준 | 1948번. 임계경로 - 위상정렬 & 다익스트라
⬛ 백준 1948번. 임계경로 - 위상정렬 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 25.
백준 | 2623번. 음악프로그램 - 위상정렬
⬛ 백준 2623번. 음악프로그램 - 위상정렬 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 24.
백준 | 14567번. 선수과목 (Prerequisite) - 위상정렬 + 레벨 탐색
⬛ 백준 14567번. 선수과목 (Prerequisite) - 위상정렬 + 레벨 탐색 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 24.
백준 | 1766번. 문제집 - 위상정렬 & 우선순위 큐
⬛ 백준 1766번. 문제집 - 위상정렬 & 우선순위 큐 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 23.
백준 | 1516번. 게임 개발 - 위상정렬 & DP
⬛ 백준 1516번. 게임 개발 - 위상정렬 & DP https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론,..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 23.
백준 | 2056번. 작업 - 위상 정렬 & DP
⬛ 백준 2056번. 작업 - 위상 정렬 & DP https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 23.
백준 | 1005번. ACM Craft - 위상 정렬 & DP
⬛ 백준 1005번. ACM Craft - 위상 정렬 & DP https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 23.
코테 | 그래프 섹션 - 다익스트라, 위상정렬 문풀
🟩 4번. 방향 바꾸기 4방향으로 갈수 있기 때문에 cost[][] 2차원 배열 생성하여 최대한 방향 적게 바꾸면서 갈 수 있는 방식 고안 PriorityQueue에 좌표 담아가면서 가중치 적은 거 우선 정렬 int dir 변수가 순서대로 dx, dy 순회하면서 방향 안바꾼 상태로 더 적은 값 갱신 가능하면 갱신 방향 바꾼 상태로 더 적은 값 갱신 가능하면 갱신 정답 출력 package to_0822_6; //다익스트라 - 방향 바꾸기 RE 풀이 import java.util.*; class Solution { static int N, M; static int[][] cost; static PriorityQueue pQ; //4방향 static int[] dx = {0, 0, 1, -1}; static ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 22.
백준 | 1261번. 알고스팟 - BFS, 다익스트라
⬛ 백준 1261번. 알고스팟 - BFS, 다익스트라 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 22.
백준 | 2665번. 미로 만들기 - 다익스트라
⬛ 백준 2665번. 미로 만들기 | 다익스트라 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 22.
코테 | 그래프 섹션 - 다익스트라 문풀
⬛ 그래프 알고리즘 🟩 1번. 최소 비행료 문제 처음에는 one-to-all 단순히 다익스트라로 접근하는 문제인 줄 알았는데, 문제 조건에 있는 정해진 ‘환승 횟수’로 제한되어 있기 때문에 레벨 탐색을 해야 한다. 다익스트라는 우선순위큐로 무조건 최소비용을 구하는 게 단순 목적인데, 여기서 레벨탐색으로 풀어야 각 레벨(거쳐갈) 당 최소 비용이 구해지기 때문에 주의 ditance[c_v]가 아닌, c_val 값으로 거리 처리 해야 답이 나온다 왜지 ? //직전 Q에서 꺼낸 값 c_val 으로 접근해야 한다. for문을 돌면서 내부에서 nx_val 값을 업데이트 하는 중이라 distance[c_v]로만 접근하게 된다면 직전에 뽑아놨던 c_val 값이 아니라 새로 갱신된 distance[c_v]로 접근하게 되..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 21.
백준 | 2468번. 안전 영역 | DFS, BFS
⬛ 백준 2468번. 안전 영역 | DFS, BFS continue 조건에 nx ≥ N, ny≥ N 했을 때 틀렸고, nx > N-1 ny > N-1 했더니 맞았다. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 18.
코테 | 강의 - 너비 우선 탐색 - BFS 섹션 - (2)
🟩 4번. 미로의 최단거리 통로 | BFS 레벨 탐색 문제이다. 출발지점 (0, 0)에서 도착점 (6,6) 까지 갈 건데 갈 때마다 lv++처리하여 dist 배열에 해당 방문한 lv들을 담아가며 처리하면 된다. 4방향 탐색할 때 변수 주의해서 사용할 것 package to_0818_2; //미로의 최단거리 통로 import java.util.*; class Solution { static int[][] dist;//거리용 //4방향 static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -1, 0, 0}; public int solution(int[][] board){ //초기화 dist = new int[7][7]; Queue Q = new LinkedList..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 8. 18.
백준 | 1303번. 전쟁- 전투 | DFS 풀이
⬛ 백준 1303번. 전쟁- 전투 | DFS, BFS문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 이 문제는 가로 크기 N, 세로 크기 M으로 준다. M먼저 입력받고, N을 나중에 입력받아서 map[N][M] 해줘야 한다. 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 16.