PS(Problem Solving)/BOJ244

• 

  [백준/BOJ] 16234번: 인구 이동 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해설 문제를 세분화해보자. 인구 이동이 더 이상 일어나지 않을 때까지 반복. 즉, 우선 무한 반복을 돌린다. 모든 나라를 bfs를 이용해서 연합이 가능한지 탐색한다.(dfs를 사용해도 된다.) 인접 국가와의 인구 차이가 l 이상 r 이하인 경우 연합을 맺는다. 연합 국가의 총 인원수를 갱신해준다. 연합 국가의 위치 정보를 저장해준다.(나는 전역으로 list를 선언해주었다.) 방.. PS(Problem Solving)/BOJ 2022. 8. 14.

• 

  [백준/BOJ] 2665번: 미로만들기 문제 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 해설 흔하게 볼 수 있는 BFS 문제이다. 미로를 탐색하며 도착점에 도달하기 위해 바꿔야하는 검은 방이 몇개인지 알아야 한다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어 지나다닐 수 있으므로, 상하좌우로 이동이 가능하다. 보통 BFS라면 방문 여부를 체크하는 배열이 있기 마련이다. 이를 통해 이미 방문했던 지점이라면 재방문을 하지 않도록 해준다. 하지만 난 이 문제에서 재방문을 허용해주었다. 모든 경우 재방문을 하는 것이 아닌, 벽을 바꾼 횟수가 .. PS(Problem Solving)/BOJ 2022. 8. 13.

• 

  [백준/BOJ] 16202번: MST 게임 문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 해설 제목에서부터 알 수 있듯이 MST를 응용하는 문제이다. 최소 신장 트리를 구하기 위해 크루스칼 알고리즘을 사용하였다. 문제에서 가장 중요한 문장은 아래 문장이다. 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다. 결론적으로는 한 턴이 끝날 때마다 가장 작은 간선을 제거하여 k만큼 .. PS(Problem Solving)/BOJ 2022. 8. 12.

• 

  [백준/BOJ] 2146번: 다리 만들기 문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 해설 문제를 해결하기 위한 과정을 생각해보자. 섬을 구분한다. 각각의 섬을 연결할 때, 최소의 다리 수로 이어질 수 있도록 한다. 크게 두 가지로 나눌 수 있다. 1번 과정부터 보자. 입력에 육지인 부분은 1로 들어온다. 나는 섬을 1, 2, 3의 번호로 나눌 것이기 때문에, 1이 들어오면 -1로 저장을 해주었다. 모든 입력을 받은 후, 아직 방문하지 않은 육지인 곳이 있다면 bfs를 수행시켜준다.. PS(Problem Solving)/BOJ 2022. 8. 11.

• 

  [백준/BOJ] 11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해설 https://jjunsu.tistory.com/249에서 했던 1916번: 최소비용 구하기 문제의 상위 버전이다. 최소 비용을 구한 후, 몇 개의 도시를 거쳤는지, 어떤 도시를 방문했는지를 같이 출력해야 한다. 최소 비용을 구하는 방법은 위 문제와 같이 다익스트라 알고리즘을 사용하여 구하면 된다. 이제 어떠한 도시를 거쳤는지 경로를 알아야 한다. 어렵게.. PS(Problem Solving)/BOJ 2022. 8. 10.

• 

  [백준/BOJ] 1956번: 운동 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 우선 초기값을 설정할 배열을 map이라 하자. map을 INF(100000000)으로 초기화해주었다. 이후 플로이드 와샬 알고리즘을 수행하여 각 정점에서 각 정점까지의 최단 경로를 구해준다. 플로이드 와샬 알고리즘의 수행이 끝났다면, 사이클을 찾아야 한다. map[i][j]와 map[j][i].. PS(Problem Solving)/BOJ 2022. 8. 9.

• 

  [백준/BOJ] 2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용해서 문제를 해결하였다. 초기값을 저장할 배열을 BooleanArray로 선언하여 입력으로 알 수 있는 학생들끼리의 관계를 true로 해준다. 이 때 배열[i][j] = true라면, i가 j보다 작다가 되고, 배열[j][i] = true라면, j가 i보다 작다가 된다. 플로이드 와샬 알고리즘을 수행하며, 배열[i][k]와 배열[k][j]가 모두 참일 시, 배.. PS(Problem Solving)/BOJ 2022. 8. 9.

• 

  [백준/BOJ] 11404번: 플로이드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해설 문제의 이름에서부터 알 수 있듯이 플로이드 와샬 알고리즘을 사용하면 된다. n의 범위가 (2 ≤ n ≤ 100)이고, m의 범위가 (1 ≤ m ≤ 100,000)이기 때문에 각 노드 사이의 비용 초기값을 10,000,000으로 설정하였다. 이 문제에서 주의할 점은 다음과 같다. 시작 도시와 도착 도시가 같은 경우는 없다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. .. PS(Problem Solving)/BOJ 2022. 8. 8.

• [백준/BOJ] 11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 플로이드 와샬 알고리즘의 기본 문제인만큼 플로이드 와샬에 대해 잘 모른다면 플로이드 와샬을 읽어보면 좋을 것이다. 0이면 간선이 존재하지 않고, 1이면 간선이 존재한다. 그렇다면 예시를 들어보자. 1 - 3은 간선이 없다하고, 1 - 2와 2 - 3은 간선이 있다고 하자. 그렇다면 1 - 2는 1이고 2 - 3은 1이므로 1 - 2 - 3이 되어 1 - 3은 간선이 존.. PS(Problem Solving)/BOJ 2022. 8. 8.

• 

  [백준/BOJ] 1520번: 내리막 길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해설 DFS로만으로 풀려다가 도저히 풀리지 않아 다른 분들이 써놓은 풀이를 참고하였다. DFS만을 이용하면 시간초과가 나게 되어 DP를 함께 사용하는 방법을 알 수 있었다. 각 현재 지점에서 4방향으로 탐색을 한다. 이 때 갈 수 있는 경우의 수를 저장하면서, DFS를 수행하게 된다. 만약 이미 탐색했던 지점이라면, 그 지점에서 갈 수 있는 경로의 수를 반환해준다. 도착 지점에 도착하게 되면 1을.. PS(Problem Solving)/BOJ 2022. 8. 8.

• [백준/BOJ] 4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 bfs로도 풀 수 있을 것 같았지만, 다익스트라를 사용해서 문제를 풀었다. 각 칸의 소지금을 우선순위 큐에 오름차순으로 기준을 잡아준다. 기본적인 다익스트라 알고리즘 문제이다. 소스 코드 import java.lang.StringBuilder import java.util.* private lateinit var map: Array private val dx = int.. PS(Problem Solving)/BOJ 2022. 8. 7.

• [백준/BOJ] 1261번: 알고스팟 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해설 상하좌우로 움직이며 목표지까지 최소 몇개의 벽을 부수어야 하는지 구하는 문제이다. bfs를 이용해서 문제를 풀었는데, 보통 bfs라면 Queue를 이용하지만 이 문제에서는 우선순위 큐(Priority Queue)를 사용하였다. 우선순위 큐를 사용한 이유는 최단거리로 가는 문제가 아닌, 최소의 벽을 부수는 문제이기 때문이다. 우선순위의 기준을 벽을 부순 개수로 오름차.. PS(Problem Solving)/BOJ 2022. 8. 6.