programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 백준에서 많이 풀어본 그래프 문제들과 비슷하다. 처음에 DFS로 풀어보려다 실패하고 BFS로 풀었다. from collections import deque def solution(n, edge): graph = [[] for _ in range(n+1)] dist = [0] * (n+1) visited = [False] * (n+1) q = deque() q.append(1) visited[1] = True for i in edge: graph[..
www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net (0, 0)에서 (M-1, N-1)까지 이동 가능한 경로의 수를 모두 구해야 하기 때문에 단순히 DFS로는 풀 수 없고, DP를 통해 메모이제이션까지 써야 한다. 1. N * M크기의 지도 m을 입력받고, dp배열을 만들고 -1로 채운다. 2. dp[i][j] = (i, j)까지 이동하는 경로의 수 3. (M-1, N-1)부터 상하좌우 방향을 탐색하며 dp[x][y]에 dfs(nx, ny)값을 더해준다. ->..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이번엔 DFS로 푼 문제이다. dfs함수: m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다. 전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다. BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데 DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는 집의 수를 ..
www.acmicpc.net/problem/1260 기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.) 그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다. DFS(Depth First Search) - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다. - 모든 노드를 방문하고자 할 때 이 방법을 쓴다. - 자기 자신을 호출하는 재귀방식을 사용한다. - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수) 단점 - BFS에 비해 조금 느리다. - DFS는 해를 구하면 탐색이 종료되므로, 구한 해가..
모르는 사이에 조금씩 조금씩..
