빅맥좋아요

https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 백준 16118번 달빛 여우 문제를 풀었다. 시작 노드에서 다른 노드까지의 최단 비용을 구하고, 간선의 가중치가 양수라서 다익스트라를 사용했다. 여우는 모든 노드를 같은 속도로 이동한다. 늑대는 2배 빠르게 이동했다가 1/2배 느리게 이동하는 것을 반복한다. 여우의 속도를 2로 두고 늑대가 빠르게 이동할 때는 1, 느리게 이동할 때는 4의 ..

https://www.acmicpc.net/problem/1486 1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net 백준 1486번 등산 문제를 풀었다. 특정 노드에서 특정 노드까지의 최단 거리를 구하고, 간선의 가중치가 양수여서 다익스트라를 사용했다. 이 문제의 경우 가장 높은 산을 갔다가 다시 호텔로 돌아와야 하므로 호텔 -> 산 -> 호텔 이런 식으로 하나의 산에 대해 다익스트라를 두 번 실행하면 된다. 실제로는 호텔 -> 산 다익스트라는 한 번 실행하면 모두 구할 수 있고, 산 -> 호텔..

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 백준 1584번 게임 문제를 풀었다. 게임에는 안전한 구역, 위험한 구역, 죽음의 구역 총 세 개의 구역이 있다. 생명력을 비용으로 생각하면 안전한 구역은 이동 비용이 0인 구역이다. 위험한 구역은 이동 비용이 1인 구역이다. 죽음의 구역엔 들어갈 수 없다. 이렇게 비용이 0과 1로 이루어졌을 때 0-1 BFS를 deque와 함께 사용할 수 있다. 다음에 이동할 구역이 방문한..

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 백준 10423번 전기가 부족해 문제를 풀었다. 최소 비용으로 연결하는 문제라서 크루스칼 알고리즘을 사용했다. plant 배열은 발전소 도시의 숫자를 저장한다. city 배열은 도시의 숫자와 전기가 공급됐는지 체크해주는 변수를 저장한다. graph 배열은 BFS 탐색용이다. 우선순위 큐와 parent 배열은 크루스칼 알고리즘용이다. 먼저 입력을 받으면서 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 백준 12100번 2048 (Easy) 문제를 풀었다. 처음에 백트래킹으로 구현을 했는데 promising한 조건을 정하지 못해서 그냥 구현 문제를 푸는 것 처럼 됐다. Move함수는 입력받은 좌표와 방향으로 숫자를 옮긴다. 재귀적으로 구현을 했다. 왼쪽으로 Move한다면 1. 입력받은 좌표의 숫자가 0인지 체크한다. 1.1 입력받은 좌표의 숫자가 0일 때, 1.1.1..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 백준 1162번 도로포장 문제를 풀었다. 간선의 가중치가 모두 양수이고 특정 노드까지의 최단 비용을 구하는 문제라서 다익스트라를 사용해야겠다고 생각했다. 기본적인 다익스트라 문제에서 추가된 것은 도로가 포장될 수 있다는 점이다. 따라서 노드 구조체에 포장된 도로의 개수를 저장하는 paved 변수를 추가해서 사용했다. dist[i][j] 배열은 포장된 도로의 개수..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 백준 1719번 택배 문제를 풀었다. 간선의 가중치가 양수이고 최단 경로를 찾는 문제라서 다익스트라를 사용했다. path 배열은 다익스트라를 수행할 때 이전 노드를 저장하는 배열이다. 예를 들어 1번 노드에서 다익스트라를 수행하면 path배열은 아래와 같이 저장된다. index 1 2 3 4 5 6 value 0 1 1 3 2 5 이 path 배열을 다르게 보면, index 노드로부터 1번 노드로 가기 위..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 백준 16236번 아기 상어 문제를 풀었다. 상어가 먹이를 찾는 부분은 BFS로 풀었다. 내가 사용한 변수는 아래와 같다. map배열 : 물고기와 아기상어의 위치를 저장 visited 배열 : BFS에서 방문했던 곳을 체크하는 용도 dist 배열 : BFS에서 좌표별로 아기 상어가 움직인 거리를 저장 Fish 구조체 : 물고기의 좌표와 거리를 저장 eatableFish 우선순위큐 : 먹을 ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 백준 1766번 문제집 문제를 풀었다. 위상 정렬 문제를 처음 풀어봤다. 이 문제 처럼 순서가 정해져 있는 작업을 수행할 때 그 순서를 결정해주는 알고리즘이라고 한다. 아래의 블로그를 참고했다. https://yoongrammer.tistory.com/86 adjList 배열은 인접리스트를 저장하는 배열이다. in_degree 배열은 본인에게 들어오는 화살표의 개수를..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 백준 9466번 텀 프로젝트를 풀었다. 처음엔 단순하게 모든 학생들을 순회하면서 DFS를 실행하고 싸이클이 존재할 때 카운트를 세는 방식을 사용했는데 시간 초과가 나왔다. 고민을 하다가 구글에 검색해서 문제 풀이를 찾아봤는데 visited 배열 말고도 done 배열을 같이 사용하는 것을 확인했다. https://wooono.tistory.com/409 위의 블로그를 참고해서 문제를 풀었다. 배열의 설명..