1. 문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2. 풀이 Point 입력을 받을 때 처음 익은 토마토의 좌표를 미리 queue에 넣어두고 그곳을 방문처리한다. 처음 입력을 받았을 때 모두 익어있을 경우가 있으므로, 이를 탐색한다 그 후 BFS 탐색을 진행하면서 토마토가 익는 경우와 익는 day를 갱신한다. 탐색을 마쳤을 때 안 익은 토마토가 있는 경우 -1 3. 소스 코드 package bfs; import ..
1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 Point 익은 토마토가 처음에 여러개가 있을 경우 동시에 진행됨을 간과함 입력을 받을 때 처음 익은 토마토의 좌표를 미리 queue에 넣어두고 그곳을 방문처리한다. 처음 입력을 받았을 때 모두 익어있을 경우가 있으므로, 이를 탐색한다 그 후 BFS 탐색을 진행하면서 토마토가 익는 경우와 익는 day를 갱신한다. 탐색을 마쳤을 때 안 익은 토마토가 있는 경우 ..
1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 Point 우선순위에 대하여 정렬하는 방법을 찾지 못함(먹이 큐를 따로 둔다는 것을 생각 못함)…. BFS를 한 번만 돌고 판단하려함 → 먹이를 먹고 난 후 우선 순위가 달라진다는 것을 생각 못함 먹이를 먹고 다시 탐색하려 할 때, 처음 상어가 있었던 위치도 다시 탐색해줘야 하는데, 이를 bfs에서 조건을 걸어주려함 → 상어가 있는 위치는 9인데, 이를 0으로 바꿔주지..
1. 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 풀이 기본적인 다익스트라 알고리즘을 활용한 문제이다. N개의 도시 = N 개의 노드, 버스의 정보 = 간선의 정보로 생각하여 인접리스트를 구성할 수 있다. 다익스트라 알고리즘을 작성할 때는 3가지를 기억하면 좋다. 최소 이동 비용을 저장할 D 배열의 초기 값을 큰 수로 저장하자. 방문처리는 BFS와는 다르게 Queue에 넣을 때 하는 것이 아니라 ..
1. 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 풀이 백준 분류에 DFS로 분류되어 있는 문제이다. 문제를 보면 학생들이 자기 자신을 팀원으로 고를 수 있고, "학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다" 라고 되어있다. 이는 노드끼리 사이클이 ..
1. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 2. 풀이 위상 정렬 문제이다. 위상 정렬이 어떤 알고리즘인지 모르거나 혹은 알고 있는데 헷갈리다면 아래 문제를 먼저 풀어보고 이 문제를 보는 것도 좋다. https://sorryday.tistory.com/76 [BOJ] 백준 2623 - 음악프로그램 풀이 1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그..
1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 위상 정렬 비순환 방향 그래프에서 정점을 선형으로 정렬한 것을 의미 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 방향 그래프(Directed Aclic Graph)여야 한다. 3. 위상 정렬 구현 방법(BFS) ..
1. 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 2. 풀이 Point 링크와스타트 (백준 15661)과 굉장히 유사한 문제이다. 주요 입력 자료구조 peopleCityMap : 도시 별로 인구수가 저장된 Map List[] linkList : 도시 별로 연결되어 있는지를 저장한 연결리스트 boolean[] visited : 도시를 2개의 구역으로 나누기 위한 배열 N개의 구역이 있을 때, A, B 구역으로 나누는 부분 visited 배열의 BackTrac..
