PS(Problem Solving)/BOJ244

• 

  [백준/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.

• 

  [백준/BOJ] 2252번: 줄 세우기 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 해설 문제의 답이 여러 개일 수 있는 스페셜 저지 문제이다. 처음에 어떻게 푸나 고민하다, 위상 정렬을 이용해서 풀었다는 글들을 많이 보았다. 위상 정렬이란 "선후 관계가 정의되 있는 그래프 구조 상에서 그에 따라 정렬하는 방법"이다. 문제의 예제1을 보면서 위상 정렬의 과정을 봐보자. 위상 정렬에는 큐를 사용하고, 또한 그래프 구조 상에서 정렬하는.. PS(Problem Solving)/BOJ 2022. 8. 15.