알고리즘/DFS BFS15 [Python] 백준 7569 토마토 🧑💻 [Python] 백준 7569 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 7576과 같은 문제이지만, 높이가 추가가 되었다 3중 포문을 쓰되, 3중 리스트 사용법을 익혀야 한 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가.. 2023. 2. 13. [Python] 백준 7576 토마토 🧑💻 [Python] 백준 7576 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가 없지만, 이 문제에서는 시작점이 1개 이상이 주어질 수 있다 두번째 for문 결과값을 탐색한다 bfs.. 2023. 2. 13. [Python] 백준 24481 알고리즘 수업 DFS (재귀!!!) 🧑💻 [Python] 백준 24481 알고리즘 수업 DFS (재귀!!!) Silver 2 - DFS 시작 기준에서 각 노드까지 얼마나 걸리는지 찾는다 문제풀이 재귀를 이용하여 DFS를 실행한다 sys.setrecursionlimit(10 ** 6) input=sys.stdin.readline 재귀를 제한해주는 식이다 (코딩 테스트에서 재귀를 사용할 때에 꼭 필요하다) 코드 import sys sys.setrecursionlimit(10 ** 6) input=sys.stdin.readline def dfs(start, count): result[start] = count for num in tree[start]: if result[num] == -1: dfs(num, count + 1) n, m, r =.. 2023. 2. 11. [Python] 백준 2644 촌수계산 🧑💻 [Python] 백준 2644 촌수계산 Silver 2 - DFS / BFS DFS도 사용할 수 있지만, BFS를 이용해서 촌수를 찾았다 부모 노드와 연결되어 있는 노드들을 먼저 탐색을 한다 탐색을 하면서 같은 번호를 찾으면 된다 문제풀이 BFS를 이용해서, 노드와 연결된 노드들 중에서 end와 같은 번호가 있는지 확인을 해야 한다 여기서 중요한 것은 while문에서 그냥 count를 넣으면, queue에서 뽑을때마다 count에 1이 더해진다 이것을 방지하기 위해, queue에 튜플 형식으로, (노드번호, 촌수)를 넣는다 코드 from collections import deque n = int(input()) start, end = map(int, input().split()) start, en.. 2023. 2. 9. [Python] 백준 1388 바닥 장식 🧑💻 [Python] 백준 1388 바닥 장식 Silver 4 - 그래프 탐색 탐색을 두 번 해야한다. 즉 2중 for문을 두번 사용한다. 탐색을 해서 '-' 가 연결되어 있는 나무 판자와 '|'가 열결되어 있는 나무 판자들의 개수를 센다 단 나무 판자의 너비는 1이다 문제풀이 2중 for문을 두번 순회를 해야 한다. 첫 번째는 가로형 나무 판자들을 찾는 것이고, 두 번째는 세로형 나무 판자들을 찾는 것이다 먼저 '-' 이면 계속 순회를 하되, 다음 판자가 '|'이면, 그 나무 판자를 count에 1을 더해준다 즉 '|'이 나타나면, '-' 의 연속 된 나무 판자가 끊겼다는 것이다 그리로 2중 for문 중 2번째 fo.. 2023. 2. 8. [Python] 백준 1260 DFS와 BFS 🧑💻 [Python] 백준 1260 DFS와 BFS Silver 2 - DFS / BFS DFS는 깊이 우선이다. 먼저 한 쪽을 선택해서, 탐색을 하는 것이다 BFS는 넓이 우선 탐색이다. 즉 부모 노드에 여러 자식 노드가 있으면, 바로 연결되어 있는 자식 노드들 부터 탐색을 한다 문제풀이 함수를 사용했다 리스트를 만들고, 리스트 안에 있는 요소들을 오름차순으로 정렬했다 (만약 길이 2개 이상이면, 숫자가 작은 곳부터 탐색을 한다) DFS 같은 경우, 재귀를 이용한다 즉 DFS는 만약 방문을 안 한 노드가 있으면, 그 노드를 다시 DFS(V)를 한다 방문을 했으면 for문은 끝까지 돌아갈 것이다. 즉 for문이 끝났다는 것은, 이미 모든 노드를 한번씩 탐색을 했다는 것이다 BFS 같은 경우 queue를.. 2023. 2. 6. 이전 1 2 다음
