[programmers] 순위 (문제 링크) 이 문제는 그래프로 분류되어 있습니다. 어떻게 그래프로 접근해야하는지 아이디어가 생각나지 않아서 어려웠던 문제입니다. 구글링을 해봤을 때 플로이드 와샬(Floyd-Warshall) 알고리즘을 이용해서 구현을 하신 답안이 많았지만 DFS로 구현했습니다. 플로이드 와샬의 경우 각 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있는 알고리즘인데 이보다는 DFS가 효율적이라고 생각했습니다. 실제로 플로이드 와샬의 시간 복잡도는 O(n^3)입니다. 풀이 방법 n = 5 results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] results의 정보를 가지고 확실한 순위를 알 수 있는 노드의 수를 찾아내는 문제입니다....
[백준] 2667번 단지 번호 붙이기 (문제 링크) 풀이 방법 graph에서 연결 요소(connected component)의 수를 찾고 연결 요소 안의 node 수를 카운트하는 문제입니다. deque로 BFS를 구현해서 해결했습니다. [0] graph와 (x,y) 좌표의 방문 여부를 표시하는 visited (list)를 생성합니다. [1] graph 전체를 순회하면서 graph(x,y) 값이 1인 경우에 bfs 함수를 실행합니다. [1-1] (x,y)를 push한 queue를 생성합니다. [1-2] queue에서 원소를 pop 합니다. [1-3] pop한 원소를 기준값으로 해서 상하좌우를 살핍니다. 만약 값이 1이고 아직 방문하지 않았다면 push 하고, 방문 표시합니다....
[백준] 2178번 미로탐색 (문제 링크) 풀이 방법 (1,1) ~ (N,M) 까지의 최단 경로를 구하는 문제이므로 BFS를 활용해서 구현합니다. 이 문제에서 BFS를 활용하여 구현하는 이유는 다음과 같습니다. Code (python) from collections import deque def bfs(root): queue = deque([root]) #큐를 생성해서 root push while queue: x,y = queue.popleft() #pop - 기본 좌표가 나옴 #상하좌우 이동 for i in range(4): nx = x + dx[i] ny = y + dy[i] #좌표 밖을 벗어나면 넘어감 if nx < 0 or ny < 0 or nx >= N or ny >= M: continue if graph[nx][ny] == 1: #만약 이동한 좌표의 값이 1이라면 graph[nx][ny] = graph[x][y] + 1 #이동한 좌표의 값에 기본 좌표 값에 1을 더함 queue....
[백준] 1260번 DFS와 BFS (문제 링크) 기본적인 그래프 탐색 문제 입니다. DFS는 stack을 활용해서 구현하고, BFS는 queue를 활용해 구현합니다. 방문할 수 있는 정점이 여러 개인 경우 숫자가 적은 것을 먼저 방문하라는 조건을 고려해야 합니다! 풀이 방법 Graph <input> 4 5 1 1 2 1 3 1 4 2 4 3 4 위의 testcase로 만들어진 그래프의 모양은 다음과 같습니다. DFS 방식으로 그래프 탐색 stack 자료구조에서 pop을 하면 나중에 들어온 것이 먼저 나옵니다....