DFS

[python] 백준 - 13023. ABCDE

🤔문제 해결 문제는 이어져있는 친구가 4명인지 물어보는 것... ( 헷갈렸다 ) 기본적인 DFS 문제이다. 중간에 조건을 줘서 잘 멈춰주기만 한다면 시간초과는 해결될 것이다. 💻소스 코드 import sys def dfs(current, cnt): global answer if answer == 1: # 답을 이미 찾았다면 dfs 멈추기 return if cnt == 5: # 답 찾았을 때 (친구가 4명) answer = 1 return visited[current] = 1 for neighbor in adj[current]: if not visited[neighbor]: dfs(neighbor, cnt + 1) visited[current] = 0 input = sys.stdin.readline ans..

[python] 백준 - 2573. 빙산

🤔문제 해결 G4 | DFS, 구현 9개월전에 풀어봤던 문제였는데, 그 때는 시간초과를 해결하지 못해서 겨우 pypy로 제출해서 통과했다. 이번에 스터디를 하다보니 다시 풀게 돼서 효율적으로 코드를 작성해 python으로도 통과를 했다. 녹이는 빙산 찾기 2차원 배열 하나씩 돌기 -> 빙산을 따로 리스트로 만들어 두기 와 DFS 빙하 덩어리가 하나인지 여러개인지 판별 DFS -> 빙산 리스트의 길이와 녹일 때 선택한 빙산의 수의 차이로 바로 계산 💻소스 코드 import sys from _collections import defaultdict input = sys.stdin.readline def melt(): melting_area = {} # 녹일 곳 dx, dy = [-1, 1, 0, 0], [0,..

[python] 백준 - 1012. 유기농 배추

🤔문제 해결 S2 | 그래프, DFS 배추밭과 배추의 위치를 2차원배열로 만든다. 배추리스트에서 하나 꺼내서 DFS로 인접한 배추들을 다 0으로 바꿔준다. 💻소스 코드 import sys input = sys.stdin.readline def find_dummy(x: int, y: int): farm[x][y] = 0 stack = [(x, y)] dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] while stack: cx, cy = stack.pop() for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결 S2 | 그래프, BFS(DFS) 단순한 그래프 문제였는데 전부다 시간초과 발생.... 다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공) 풀이방법은 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다) 모든 노드에 대해서 BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다. 가장 높은 카운트의 노드들을 출력한다. 다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지... 💻소스 코드 import sys from collections import defaultdict from collections import deque def bfs(start): q = deque([start]) visited = [0] * (N ..

깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란 깊이를 우선으로 하여 탐색을 수행하는 알고리즘 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법! ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것! 경로를 찾고 싶을 떄 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 ) 스택으로 사용시 이웃 중 가장 뒤에 있는 것부터, 재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다. 📔 깊이 우선 탐색(DFS) 구현 def dfs(c): print(c, end=' ') for neighbor in adj[c]: # c의 이웃 중 if visited[neighbor] == 0: # 방문 아직 안한 친구이면 visited[neig..

[python] 백준 - 16953. A → B

🤔문제 해결 S1 | 그래프, BFS 난 DFS 알고리즘 분류에는 그래프와 BFS로 나와있는데 잘 모르겠고, DFS로 해결했다. 목표 숫자부터 두가지 경우로 나눠서 들어간다. 맨 끝의 숫자가 1이면 1을 버리고 재귀 맨 끝의 숫자가 1이 아닐 때 2로 나누어 떨어지면 2로 나누고 재귀 테스트 케이스 3번을 예시로 하겠다 ( 100, 40021 ) 40021: 맨 끝의 숫자가 1이므로 1을 버린다 40021 => 4002 체크하는 방법은 10으로 나눈 나머지, 버리는 방법은 10으로 나눈 몫 4002: 맨 끝의 숫자가 1이 아니고 2로 나누어 떨어지므로 2로 나눈다. 4002 => 2001 2001: 버린다. 2001 => 200 200: 나눈다. 200 => 100 100: 100 == A 이므로 그만!..