개발하는 개구리

🐸 문제 정보 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 38.36m 📝 풀이 cycle을 찾으면 되는 문제인 것은 알겠으나... 구현하는 것이 생각보다 어려웠던 문제였다ㅠㅠ DFS로 푸는데, 이번에 확인할 노드를 인자로 전달 받아서, 시작했던 노드와 다시 만나면 res에 해당 노드를 넣어주는 방식으로 풀었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) g..

🐸 문제 정보 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 07.51m 📝 풀이 MST 같아 보이지만 DFS 문제이다. 입력 값을 바탕으로 양방향 그래프를 만들어주고, 방문했는지 체크할 visited도 만든다. 이후 그래프를 돌면서, 연결된 노드는 모두 방문처리하고, 방문하지 않은 노드에서 다시 dfs를 시작할 경우 결과 값에 1 더해준다. 🧑‍💻 나의 답 # pypy3 import sys input = sy..

🐸 문제 정보 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 dfs ⏱️ 풀이 시간 22.22m 📝 풀이 처음에 그냥 가중치 그래프 보자마자 허겁지겁 bfs로 풀어버렸다.. 15분 쯤 되어서야 뭔가 이상함을 감지하고 dfs로 변경했다. 하지만 dfs도 n과 m의 범위가 커지면 통과하지 못할 것 같다는 생각이 들었는데, 아니나 다를까 문제에 표기된 알고리즘은 DP였다. 아마 Large에서는 DP로 풀어야 통과되지 않을까 싶다. 우선 이 여기에서는 간단하게 방향을 잡아..