PS(Problem Solving)245

• 

  [백준/BOJ] 13424번: 비밀 모임 문제 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 해설 각 방 사이 비밀 통로를 이용하는 비용이 나와있다. 플로이드 와샬 알고리즘을 이용하여 각 방 사이를 오가는데 필요한 최소 거리를 구해놓은 후, 현재 친구들이 있는 방에서 각 방까지 가장 작은 비용으로 갈 수 있는 방을 찾으면 된다. 코드 import java.util.* import kotlin.collections.ArrayList import kotlin.math.min privat.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 15644번: 구슬 탈출 3 문제 https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전 문제인 구슬 탈출 2문제랑의 차이점은 출력에 경로가 추가된 것밖에 없다. 앞부분은 구슬 탈출 2문제랑 같으므로 저 글을 확인하도록 하자. 이제 경로를 추가해야 한다. 데이터 클래스에 경로를 저장할 route라는 변수를 추가해주었다. 이제 움직인 방향에 따라 왼쪽이라면 "L", 오른쪽이라면 "R", 위라면 "U", 아래라면 "D"를 .. PS(Problem Solving)/BOJ 2022. 9. 6.

• 

  [백준/BOJ] 13459번: 구슬 탈출 문제 https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전에 구슬 탈출2 문제를 풀고 구슬 탈출1문제도 있을 것 같아 검색해보니 역시나 있었다. 구슬 탈출2 이 글을 보고 오는 것을 추천한다. 이 문제와 구슬 탈출2 문제는 출력에만 차이가 있고, 다를 것이 없다. 구슬 탈출2 문제에서는 빨간 구슬이 탈출하는데 최소 몇 번 움직여야 하는지를 출력하는 것이고, 이 문제는 탈출할 수 있다면 1, 없.. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 13460번: 구슬 탈출 2 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 빨간 구슬과 파란 구슬 두개가 있다. 이 중 10번 이하로 움직여서 빨간 구슬만이 구멍에 들어가게 해야한다. 만약 두 구슬 모두 구명에 빠지는 경우 -1을 출력하게 된다. 처음에는 빨간 구슬을 관리할 큐, 파란 구슬을 관리할 큐 이렇게 두개를 만들어 문제를 해결하려 했다. 하지만 한개의 큐로 모든 정보를 다 담고 하는 것이 더 나을 것 .. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 2638번: 치즈 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 해설 문제에서는 치즈의 외부 공기와 내부 공기로 나뉘어 있다. 외부 공기에 2면 이상이 닿아있다면, 그 부분은 녹는다. 내부 공기에 닿은 것은 무시하여도 된다는 것이다. 따라서 문제를 크게 나눠보면 다음과 같다. 외부 공기와 내부 공기를 구분한다. 현재 위치에 있는 치즈가 두 면 이상이 닿았는지 확인하고, 2면 이상 닿아있다면 그 치즈를 녹인다. 더 녹일 치즈가 있는지 확인한다... PS(Problem Solving)/BOJ 2022. 9. 4.

• 

  [백준/BOJ] 2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 해설 두 회원이 친구 사이라면 1, 친구의 친구 사이라면 2, 친구의 친구의 친구 사이라면 3 ... 과 같이 숫자가 증가한다. 예를 들어 1, 2, 3의 회원이 있을 때, 1번 회원과 2번 회원이 친구 사이이고, 2번 회원과 3번 회원이 친구 사이라면 1번 회원과 3번 회원은 친구의 친구 사이이므로 2의 값을 가지게 된다. 즉, 한 다리를 거쳐 알 수 있다는 것이므로 플로이드 와샬 알고리즘.. PS(Problem Solving)/BOJ 2022. 9. 3.

• 

  [백준/BOJ] 1507번: 궁금한 민호 문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 해설 플로이드 와샬 알고리즘을 역으로 이용하여 문제를 해결할 수 있다. 플로이드 와샬 알고리즘을 생각해보자. 만약 1번 도로, 2번 도로, 3번 도로가 있을 때, 1 - 2, 2 -3번 간 도로가 있다면 1 - 3번 도로는 없어도 1 - 2 -3을 통해 갈 수 있다. 즉 map[1][3] == map[1][2] + map[2][3]이 되는 것이다. 따라서 이 문제에서는 m.. PS(Problem Solving)/BOJ 2022. 9. 3.

• 

  [백준/BOJ] 16197번: 두 동전 문제 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 해설 두 동전 중 하나만 보드에서 떨어트리기까지 최소 몇번을 움직여야 하는지 구해야하는 문제이다. bfs를 이용하여 문제를 해결할 수 있다. bfs를 수행할 때 방문여부를 체크하는데, 이 문제에서는 동전이 2개이며 각각의 (y, x)좌표를 갖고 있으므로 4차원 배열을 이용하여 방문여부배열을 선언해야 한다. 즉, 다음과 같이 선언된다. visited[row][col][row][col] 입력을.. PS(Problem Solving)/BOJ 2022. 9. 2.

• 

  [백준/BOJ] 1719번: 택배 문제 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 응용하여 문제를 해결할 수 있다. 플로이드 와샬을 진행하므로 자기 자신으로 향하는 노드는 0으로, 그 외에는 INF(임의로 지정)으로 초기화해준다. 이후 간선의 정보를 입력받아 어떠한 노드에서 어떠한 노드로 향할 때 얼마의 비용이 드는지를 저장해주고, a->b와 같이 한 번에 갈 수 있는 노드들은 경로를 저장해 줄 배열 path[a][b] = b와 같이 된.. PS(Problem Solving)/BOJ 2022. 9. 1.

• 

  [백준/BOJ] 1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 해설 N-1개의 길만을 남겨야 한다. 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 위 3 문장은 문제에서 가장 핵심이 된다 생각한 것들이다. 우선 1, 2번을 보면 최소 신장 트리를 구해야 한다는 것을 알 수 있다. 이때, 문제에서는 각 나라에 .. PS(Problem Solving)/BOJ 2022. 8. 31.

• 

  [백준/BOJ] 1613번: 역사 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 해설 n개의 사건들의 전후 관계가 주어진다. 이를 통해 두 개의 사건의 전후 관계를 알아낼 수 있는지, 안다면 먼저 일어났는지, 후에 일어났는지를 알아내면 된다. 플로이드 와샬 알고리즘을 이용하면 모든 사건들의 전후 관계를 한번의 알고리즘 수행으로 알아낼 수 있다. 전후 관계를 표시할 배열들을 초기값(INF = 987654321이라 하자.)으로 선언해준다. 이때 같은 사건(i == j.. PS(Problem Solving)/BOJ 2022. 8. 30.

• 

  [백준/BOJ] 14938번: 서강그라운드 문제 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 해설 어떠한 지역에 떨어졌을 때, 수색 범위 안에서 가장 많은 아이템을 얻을 수 있는지를 구하는 문제이다. 우선 모든 지역에서의 범위를 구해야 하기 때문에 1번 지역에 떨어졌을 때 모든 지역까지의 거리를 구해야 하고, 2번 지역에 떨여졌을 때 모든 지역까지의 거리, 3번, 4번 . . . n번에 떨어졌을 때의 모든 지역까지의 거리를 구해야 한다. 모든 지역까지의 거리를 구하는 알고리즘으로 다익스트.. PS(Problem Solving)/BOJ 2022. 8. 29.