https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡IDEA BFS를 사용하여 구현하는 문제이다. 인구 이동 조건에 따라 구현하는 과정 중 인접한 나라 중 인구 차이가 L이상 R이하인 나라끼리 연합을 맺는다는 부분에서 BFS를 사용해야 한다. 상하좌우로 인접한 나라가 범위 내에 있고, 방문하지 않았고, 현재 나라와의 인구 차이가 L이상 R이하라면 큐에 추가해주는 식으로 구현했다. 이 때 연합한 나라들을 저장해두는 union 배열에도..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 💡IDEA 문제의 조건대로 구현해야 한다. 네 개의 톱니바퀴를 어떤 방향으로 돌려야 하는지 알아야 하는데, 현재 바퀴와 맞닿은 바퀴들의 방향도 조정해주어야 한다. 이 과정에서 나는 BFS를 사용했다. 현재 바퀴의 번호를 바탕으로 인접한 바퀴의 맞닿은 부분이 같은지 다른지 판단하여야 한다. 왼쪽과 닿는 것은 현재 바퀴의 -2번째와 왼쪽 바퀴의 2번째이고, 오른쪽과 닿는 것은 현재 바퀴의 2번째..
https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 음식물이 있는 곳(1)과 없는 곳(0)을 구별하여 음식물이 있는 곳에서 BFS를 돌며 상하좌우로 연결된 음식물을 찾는다. 음식물을 찾으면 음식물이 없다고 갱신해주고, 개수를 센다. 이런식으로 하면 굳이 방문배열을 만들지 않고도 입력받은 맵 배열 하나로 해결된다. BFS를 돌면서 음식물이 없어지기 때문에, 음식물이 있는..
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 💡IDEA DFS 또는 동적 계획법을 사용하는 문제이다. 1463. 1로 만들기 문제와 거의 동일한데, N을 1로 만드는 방법에 포함된 수를 출력해야 한다는 점이 달랐다. 1463번에서 사용했던 그대로 DFS를 수행하지만 왔던 길을 기억하는 path를 저장했다. N에서 세가지 방법으로 1을 만들었을 때 연산 횟수의 최솟값을 갱신하는 과정에서 path도 갱신해주면 된다. 문제 분류에 동적 계획법도 있어서 한 번 도전해보았는데, 메모리도 시간도 꽤나 많이 잡아먹어서 DFS로 푸는 쪽이 좋을 것 같다. 그래..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 자주 접했던 문제라 정말 금방 풀었다. 조금 다른 점은 방향이 8방향 인 점 정도이다. 모든 행열을 돌면서 섬이 있는 곳을 발견하면 거기서부터 갈 수 있는 모든 곳을 탐색하고 방문 기록을 한 후 돌아온다. BFS를 한 번 수행하는 게 한 번 카운트 하는 것이다. 방문 기록은 따로 배열을 만들기보다 기존에 받아온 이차원 배열에서 섬(1)인 곳을 바다(0)..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 💡IDEA DFS와 백트래킹을 사용하는 문제이다. 문제 자체는 쉽게 접근이 가능하지만 시간초과가 자꾸 발생해서 꽤 고생을 했다. 처음에는 방문 배열에 알파벳 자체를 넣었다 뺐다 하는 식으로 했지만 바로 시간초과가 발생했다. 알파벳을 쉽게 인식할 수 있는 방법을 생각해보다가 알파벳을 숫자로 바꾸어주는 ord 함수를 사용해서 알파벳 개수인 26개만큼의 길이의 배열을 만들어서 사용하기로 했다. ..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 규칙을 찾기 위해서는 직접 계산해보면서 찾는 것이 빠르다. K \ N 1 2 3 4 5 1 1 1 1 1 1 2 2 3 4 5 6 3 3 6 10 15 21 4 4 10 20 35 56 5 5 15 35 70 126 위의 표 처럼 K와 N 값에 따른 0부터 N까지 정수 K개를 중복 허용하여 더해서 N이 되는 경우의 수를 계산할 수 있다. K=1인 경우, 정수를 한 개만 사용해서 N을 만드는 경우는 N 한 경우 뿐이므로 모두 1이다. N=1인 경우, 정수 K개로 1을 만드는 경우는..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 2293. 동전 1 문제를 풀었던 것이 도움이 되었다. 가치의 합이 최대 10000이므로 10001 길이의 dp 배열을 사용해야 한다. 가치의 합이 0인 경우는 없으므로 0으로 초기화하고, k번째까지 dp를 구한다. 현재 동전을 포함하는 경우와..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 이 문제는 맥주를 50미터마다 하나씩, 20개씩 한 상자를 꾸준하게 마시고 편의점에서 채운다는 맥락에서 결국 1000미터 안에만 편의점이 있으면 된다는 것이 중요하다. 일반적인 BFS와 거의 유사하지만, 좌표 범위가 -32768 ≤ x, y ≤ 32767이므로 자주 사용하던 이차원 배열의 방문 확인용 배열을 만들기보다 그냥 방문한 좌표 자체를 저장하는 ..
