728x90

dfs 2

[python] 프로그래머스 - FloodFill

FloodFill과 그래프 탐색 floodfill 같은 경우엔 주어진 시작점으로부터 연결된 영역의 크기를 구하는 문제이다. (하나의 알고리즘으로 분류되는 듯하다) 프로그래머스 스터디에 참가하면서 floodfill 이라는 문제를 오래 붙잡고 있었는데, 이런 문제는 쉽게 접근하자면 모든 점마다 bfs, dfs를 수행하면서 영역 별로 "조져주는" 것이 해결책임을 알아냈다! 한 번의 탐색만으로는 수행이 불가능하다. (모든 정점을 한 번씩만 방문하는 걸로는 해결이 안된다는 의미) 처음에는 dfs 풀이만을 생각해냈는데, 한 번의 dfs만으로 풀이하려 했기에 해당 풀이도 오류가 떴다 (당시엔 몰랐음 ㅎㅎ... 컴퓨터는 죄가 없다. 코드를 짜는 나에게 있다 죄는 ^^). bfs로는 도저히 어떻게 푸는 건지 감이 안와서..

[파이썬(Python) 자료구조] DFS (깊이 우선 탐색) , BFS (너비 우선 탐색)

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다. python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다. graph = { 1: [2,3,4], 2: [5], 3: [5], 4: [], ... } DFS (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..

728x90