본문 바로가기
728x90

DFS37

[Python] 백준 4963 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해결 움직일 수 있는 방향이 동서남북 대각선까지 총 8가지이다. 한 점을 잡고 갈수 있는 끝까지 가면서 Land를 Sea로 바꾸는 작업을 한다. 더이상 갈 수 없으면 다음 Land점을 잡고 똑같은 일을 한다. 이를 DFS로 코드를 만들 수 있다. 백준은 sys.setrecursionlimit()를 꼭 써야하는 것 같다. CODE import sys input = sys.stdin.rea.. 2023. 1. 22.
[python] 백준 11724 연결 요소의 개수 https://www.acmicpc.net/problem/11724 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 문제 해결 그래프가 몇개로 분리되어있는지 개수를 세는 문제 visited 리스트를 통해 지나간 점을 체크하면서 1번부터 n번까지 dfs나 bfs를 돌리면서 몇번 돌려야 visited 리스트 원소가 모두 True가 되는지 count 한다고 생각하면 된다. CODE(dfs) import sys sys.setrecursionlimit(500.. 2023. 1. 22.
[python] 백준 15661 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 해결 팀을 정하는 것부터 하나 하나 다 해봐야 하기 때문에 상당히 시간복잡도가 클 것 같다.(팀원 수도 양수라는 것 외에 정해지지 않음) 결국 팀원 하나하나 정하는 것을 재귀를 통해서 정리하고 계산을 하여 최솟값을 구한다. 파이썬으로는 시간초과가 나와서 pyp3로 풀었다. CODE import sys input = sys.stdin.readline.. 2023. 1. 16.
[python] 백준 10971 외판원 순회2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제해결 dfs 는 써야된다는 생각이 바로 든다. (계속 반복적으로 판별하여 이동하므로) 마지막에 처음 시작지점으로 돌아와야 하므로 처음 시작점은 기억해두어야한다. 현재 지점(now)에서 이동할 지점(next)로 갈 때 주의할 점은 한번도 가본적이 없어야 한다는 것(단 시작점으로 마지막 이동할 때 제외)과 지금 비용이 최소비용일 가능성이 있어야 한다는 .. 2023. 1. 11.
728x90