본문 바로가기
728x90

전체 글423

[Python] 백준 16947 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제 해결 각 점(역)이 cycle 안에 들어가는지 확인해야한다. 이는 DFS를 통해 한바퀴 돌아 다시 출발한 점으로 올 수 있는지 확인한다. 2호선은 순환선이 한 개이지만 문제에서는 두개일 수도 있고 알 수 없다. 그래서 한번 사이클 만들었다고 끝이 아닐 수 있다. (모든 점에서 사이클을 돌려서 안에 있는지 확인해야한다는 점이다.) cycle안에 있는 점은 거리가 0으.. 2023. 1. 24.
[python] 백준 16929 Two Dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 해결 DFS를 이용하기 좋다고 생각되는 문제 Cycle을 만들면 되므로 시작점에서 출발하여 방문하지 않은 길로 가서 다시 시작점으로 돌아올 수 있으면 cycle이 만들어지므로 바로 print("Yes") 출력하고 exit()를 통해 코드 종료 시작점을 (0,0) 부터 (n-1,m-1) 까지 m*n 개를 모두 돌리는 것이 마음에 안들지만 다른 방법이 생각이 안난다...ㅜㅜ 시작점을 기.. 2023. 1. 23.
[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.
728x90