DFS

[python] SWEA - 1248. 공통조상

🤔문제 해결 D5 | 그래프 이진 트리를 만들어서 문제를 해결하자. 이런식으로 2차원 배열을 만든다. 길이가 3인 리스트가 V개인 2차원리스트 부모 노드들 찾기첫 노드 (여기서는 8 과 13) 에서 시작해서 부모 노드를 타고 쭉 올라간다. ( DFS ) 8 의 부모 노드는 [5, 3, 1] 13의 부모 노드는 [11, 6, 3, 1] 공통 부모 노드 찾기 앞에서부터 for문을 돌며 겹치는 친구 찾고 바로 나오기 (여기서는 3) 공통 부모 노드 크기 찾기 노드(여기서는 3)에서 자식 노드를 타고 쭉 내려가면서 개수를 세어준다(DFS) 💨 💻소스 코드 def find_parent(n, parent_list): if tree[n][2]: parent_list.append(tree[n][2]) find_pare..

[python] 프로그래머스 - 여행경로

🤔문제 해결 Lv3 | DFS 간단한 DFS 문제인줄 알았지만 조금 복잡한 문제이다. 그냥 풀면 테스트케이스 1,2번이 틀리게 된다. 이유는 중간에 길이 끊어지면 안되기 때문.예를 들어 이런 테스트 케이스가 있다고 했을 때 - ( 예외 케이스 ) 위와 같이 두가지 경로가 나올 것이다. 문제에서는 오름차순대로 진행하라고 했지만 B를 먼저가게 된다면 모든 티켓을 이용할 수 없기 때문에 답이 되지 않는다. 여기서 D까지 갔다가 길을 못찾고 A로 다시 돌아가야 하는데 어떻게 할까 고민하던중 길이 끊어진 D가 마지막이겠다 라고 생각해서 경로를 거꾸로 넣기로 했다. 길이 끊어져 있는 answer에 D를 저장하고, D가없어지면 B도 끊어진다. answer 에 B를 저장한다. 하지만 A는 B가 없어도 C가 있기 때문에..

[python] SWEA - 1219. [S/W 문제해결 기본] 4일차 - 길찾기

🤔문제 해결 1. D4 | DFS 스택 2. 인접리스트를 만든다. 3. DFS 탐색을 한다. 4. 끝점을 만나면 answer = 1 아니면 그대로 answer = 0 을 출력한다. 💨 DFS 기본 문제 💻소스 코드 for _ in range(1, 11): tc, n = map(int, input().split()) # 인접 리스트를 만든다. # {1:[2,3], 2:[4,8]} # 1에서 2와 3으로 갈 수 있고, 2에서 4와 8로 갈 수 있다는 의미 adj_list = list(map(int, input().split())) adj = {x:[] for x in range(100)} for i in range(0, n*2, 2): s = adj_list[i] e = adj_list[i+1] adj[s]..

[python] SWEA - 7465. 창용 마을 무리의 개수 / 10200. 구독자 전쟁

1. 창용 마을 무리의 개수 문제 해결 D4 | DFS, BFS, 그래프 1. 주어진 정보로 인접리스트를 만든다. 2. 보통의 그래프 탐색이라면 시작점하나로 BFS나 DFS 탐색을 하고 끝나지만 여기서는 모든 노드를 탐색해야 하므로 3. BFS탐색을 하는 while문을 for문으로 감싸서 모든 노드를 탐색한다. 4. for문을 통해 큐에 들어가는 노드는 한 무리의 시작점이므로 카운트를 세어준다. 🌦 처음 실패는 while 문 안에 for 문을 넣어 시간초과가 났다는 것이다. 여기서 for 문을 바깥으로 꺼내주고 시간초과는 해결, 두번째 실패는 for문을 N까지 돌려서 났다. N+1로 고쳐서 통과했다. 소스 코드 from _collections import deque for tc in range(1, 1 ..

[python] 백준 - 4963. 섬의 개수

문제 해결 1. DFS or BFS를 이용해 몇개의 무리가 있는지 알아내는 문제이다. 2. while문 한 싸이클이 돌 떄마다 한무리를 체크할 수 있다. 3. visit배열을 따로 만들어 사용하거나, 지나온 곳을 다른값으로 바꿔주는 방법을 이용한다. 소스 코드 from _collections import deque while True: w, h = map(int, input().split()) if w == 0 and h == 0: break island = [list(map(int, input().split())) for _ in range(h)] # 상 우상 우 우하 하 좌하 좌 좌상 # 8방향 탐색을 위해 dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 1, 1, 1, 0..