문제 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 분류는 구현으로 되어 있었는데, 그래프 탐색으로도 풀 수 있는 문제였다. 문제의 힌트가 중요한데, 친구의 친구까지만 결혼식에 초대가 가능하다는 점이다. 따라서 1번 노드(상근이)를 시작으로 너비 우선 탐색을 진행하면서 거리(dist)가 2 이하인 노드들만 개수를 세주면 된다. 코드 import sys from collections import defaultdict, deq..
문제 https://www.acmicpc.net/problem/1325 max_cnt: max_cnt = cnt results.append([i, cnt]) for i, cnt in results: if cnt == max_cnt: print(i, end = ' ')
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 백트래킹을 이용하거나 combination 함수를 사용하는 두 가지 방법으로 풀 수 있다. 문제 자체의 난이도는 그렇게 높지 않았지만, "최소 한 개의 모음과 최소 두 개의 자음으로 구성되어있다."라는 제약 조건에 대한 처리를 해주지 않으면 테스트케이스는 통과하더라도 틀릴 수 있는 문제였다. 나는 두 가지 방법으로 다 풀어봤는데, 속도적인 측면에선 combination 함수를 사용하는 편이 ..
문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 언뜻 문제만 DFS를 이용해 백트래킹을 해야 하는 문제로 보인다. 하지만 이 문제는 최단 경로를 구하는 일차원 그래프 탐색 문제였다. 오히려 다른 BFS문제들보다 더 심플하다. 방문처리만 조금 신경써준다면 수월하게 해결할 수 있다. 미리 그래프의 크기만큼의 리스트를 선언하거나 집합을 이용해서 O(1) 안에 방문처리를 해줄 수 있도록 하자. 코드
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 유사한 문제를 이미 풀어본 적이 있다. BFS문제였다. 다만, 탐색을 시작할 좌표(g[i][j] == 1)가 여러 개이기 때문에 탐색을 시작하기 전에 이 좌표들을 모두 큐에 담아주는 것이 중요했다. 좌표를 모두 큐에 담지 않으면 최적해를 구할 수 없다. 처음 입력을 받을 때부터 큐에 담아주면 좀 더 빠르게 탐색을 진행할 수 있다. 코드
