PS(Problem Solving)245

• 

  [백준/BOJ] 16928번: 뱀과 사다리 게임 문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해설 총 100개의 칸으로 이루어진 보드판에서 주사위를 굴려 100번째 칸에 도달할 수 있는 최소 횟수를 구하는 문제이다. 문제의 조건으로 100번 칸을 넘어가면 이동할 수 없으므로, 딱 100번째 칸에 도달했을 때의 값을 구해야 한다. 우선 뱀과 사다리 각각 어떠한 칸에 놓여 어떠한 칸으로 입력되는지를 저장해놓기 위해 두 개의 Map을 선언하였.. PS(Problem Solving)/BOJ 2022. 8. 28.

• 

  [백준/BOJ] 1660번: 말이 되고픈 원숭이 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 해설 출발점에서 도착점까지 움직일 때, 최소로 움직일 수 있는 값을 출력하는 문제로 BFS를 사용하여 문제를 풀 수 있었다. 원숭이는 상하좌우로 움직일 수 있고, k번 이하로 말처럼 움직일 수 있다고 한다. 나는 이를 말이 움직일 수 있는 좌표와 원숭이가 움직일 수 있는 좌표로 각각 저장해주었다. private val monkeyX = intArrayOf(1, -1, 0, 0.. PS(Problem Solving)/BOJ 2022. 8. 26.

• 

  [백준/BOJ] 17472번: 다리 만들기2 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해설 문제를 읽어보면, 크게 3가지 과정을 나눠야하는 것을 알 수 있다. 섬을 구분짓는다. 섬을 잇는 다리를 놓는다. 모든 섬이 연결되었는지 확인 및 다리의 총 길이를 구한다. 단계별로 나가보자. 우선 섬을 구분지어야 한다. 나는 우선 섬으로 표시된 1을 전부 -1로 저장해주었다. 이후 BFS를 사용하여 섬에 번호(1, 2, 3, 4, . . .)를 붙여주었다. repe.. PS(Problem Solving)/BOJ 2022. 8. 25.

• 

  [백준/BOJ] 10159번: 저울 문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 해설 전형적인 플로이드 와샬 알고리즘 문제이다. 플로이드 와샬 알고리즘을 사용하는 문제이므로 우선 물건의 개수만큼의 이중 배열을 선언한다. 나는 이 배열을 boolean 배열로 하였지만, 다른 배열로 하여도 설정만 잘하면 크게 상관없다. 물건 쌍의 개수를 입력받으면, 배열에서의 그 인덱스를 true로 한다. 이는 양방향이 아닌 1 > 2처럼 단방향이므로 한쪽으로만 정.. PS(Problem Solving)/BOJ 2022. 8. 24.

• 

  [백준/BOJ] 2636번: 치즈 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 해설 판의 가장자리에는 치즈가 놓여있지 않다고 문제에 나와있다. 즉, (0, 0)의 위치 또는 각 판의 가장자리 어디서든 bfs 혹은 dfs를 이용하여 탐색을 해나가면 안에 공기에 접해있는 치즈만을 녹일 수 있다. 치즈가 전부 녹을 때까지 bfs를 수행해줘야 한다. 따라서 bfs를 한 번만 수행하는 것이 아닌, 모든 치즈가 사라질 때까지 반복을 해야 한다. 이를 알기 위해 bfs를 수행하는 과정에서 1(치즈)이.. PS(Problem Solving)/BOJ 2022. 8. 23.

• 

  [백준/BOJ] 2493번: 탑 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 해설 탑이 n개 있고, 이 탑들은 좌측으로 신호를 보낸다. 좌측에 현재 탑보다 더 높은 탑이 있다면 신호를 받을 수 있고, 더 높은 탑이 없다면 신호를 받을 탑이 존재하지 않는다는 의미이다. 문제의 예시를 보며 차근차근 알아가보자. 맨 처음 탑은 좌측에 아무 것도 없기 때문에, 신호를 받는 탑이 없다. 즉 0을 출력한다. 이제 이 탑을 스택에 넣어줄 것이다. 높이가 9인 2번 탑에서 신호를.. PS(Problem Solving)/BOJ 2022. 8. 22.

• 

  [백준/BOJ] 1082번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 해설 한 컴퓨터가 해킹당했고, 이 컴퓨터에 의존하는 컴퓨터들은 시간이 지남에 따라 전염되기 시작한다. 즉, 한 개의 루트 노드로부터 연결된 노드들이 전부 감염된다는 것이다. 이를 풀기 위해 다익스트라 알고리즘을 응용하였다. 다익스트라 알고리즘은 최단 경로를 찾는 알고리즘으로 PriorityQueue를 이용하여 수행해나간다. 하지만 이 문제에서 a, b는 두 번 이상 주어지지 않는다. 즉, 최단 .. PS(Problem Solving)/BOJ 2022. 8. 21.

• 

  [백준/BOJ] 1967번: 트리의 지름 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해설 한 정점에서 가장 멀리 있는 정점은 원의 지름 즉, 테두리에 해당되는 정점이다. 따라서 한 정점에서 가장 멀리 있는 정점을 구한 후, 그 정점에서 가장 멀리 있는 정점까지의 길이가 곧 원의 지름이 된다. 우선 가장 멀리 있는 한개의 정점을 구해야 한다. 이때 어떠한 정점에서 출발을 하든지 간에 가장 멀리 있는 정점은 지름에 해당하는 정점 중 하나이다. 지름에 해당하는.. PS(Problem Solving)/BOJ 2022. 8. 20.

• 

  [백준/BOJ] 2470번: 두 용액 문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 해설 이분 탐색을 이용하여 해결할 수 있는 문제이다. 용액들의 특성값을 배열 혹은 리스트에 넣고, 이를 정렬시킨다. 이제 두 개의 포인터를 잡는다. 한개는 배열의 시작 위치인 0, 또 하나는 배열의 마지막 위치인 n - 1로 잡는다. list[start] + list[end]가 0보다 작다면, 두 수의 값이 0에 더 가까워질 수 있도록 start를 증가시켜준.. PS(Problem Solving)/BOJ 2022. 8. 19.

• 

  [백준/BOJ] 3055번: 탈출 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 해설 각 맵에 입력되는 정보 당 상태를 보자. D: 비버 굴 .: 빈 공간 *: 물 S: 고슴도치 X: 돌 고슴도치는 비버 굴로 이동해야 하며 물 또는 돌이 있는 공간은 지나갈 수 없다. 또한 물은 1분마다 인접한 칸으로 번져나간다. 즉, BFS를 두번 실행시켜야 한다는 것이다. 우선 각 빈 공간에 물이 몇 분이 지났을 때 차는지를 구하는 BFS를 수행한다. 이 과정이 끝났다면, 몇 분 후에 칸에 물이 .. PS(Problem Solving)/BOJ 2022. 8. 18.

• 

  [백준/BOJ] 12893번: 적의 적 문제 https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 해설 A와 B가 적대 관계고 B와 C가 적대 관계라면, A와 C는 우호 관계가 된다. 이 때, C와 D가 적대 관계라면, A와 C가 우호 관계이고, B와 D가 우호 관계가 된다. 결론은 두개의 팀으로 나눈다는 것이다. 즉, 이분 그래프가 성립이 되는지 안되는지를 구하는 것이다. 이분 그래프의 설명은 이 글을 참고하면 좋다. 코드 import j.. PS(Problem Solving)/BOJ 2022. 8. 17.

• 

  [백준/BOJ] 1707번: 이분 그래프 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 해설 처음 문제를 풀 때, 이분 그래프를 트리처럼 사이클이 없는 그래프라고 생각하였어서 계속해서 틀렸습니다가 떴다. 백준의 질문 검색을 통해 질문을 하였고, 금방 댓글이 달려 이분 그래프가 나의 생각과는 완전히 다르다는 것을 알고 이분 그래프에 대해 공부를 한 후 문제를 풀어보았다. 이분 그래프에 대한 설명은 이 글을 읽어보면 도움이 될 것이다. 이 문제에서 주의할 점은 특정 정점에서만 이분.. PS(Problem Solving)/BOJ 2022. 8. 16.