DFS3 [백준] 1520: 내리막 길 python 구현 / DFS, DP 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 풀이 D.. 2023. 3. 14. [백준] 2606: 바이러스, python 구현 / 출력 초과 Error 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. code 현재는 adjacency matrix를 사용하여 구현하였지만, 사실 adjacency list를 사용하는 것이 메모리 효율측면에서 월등하다고 한다 ! 만약 가중치를 가지는 그래프라면 Node[1] = [(2, 4), (3, 1), ...] 와 같이 튜플로 (node, weight)를 표현할 수 있음 ! n = int(input()) pair_n = int(input()) adj_mat = [[0]*n for _ in range(n)] for _ in range(pair_n): x, y = .. 2023. 2. 20. [백준] 1260: DFS와 BFS, python 구현 1. 입력 코드 구현 해당 코드에서 인접 리스트가 정렬되어야 작은 수를 우선으로 탐색한다. DAT(Direct Access Table)를 위한 visited 변수를 만듦 node, edge, st_node = map(int, input().split()) adj_list = [[] for _ in range(node+1)] for _ in range(edge): i, j = map(int, input().split()) adj_list[i].append(j) adj_list[j].append(i) adj_list = [sorted(i) for i in adj_list] visited = [0]*(node+1) 2. DFS 구현 dfs는 깊이 우선 탐색이기 때문에 stack으로 구현한다. 노드를 받기위한 .. 2023. 2. 20. 이전 1 다음
