BFS

[python] 백준 - 1261. 알고스팟

🤔문제 해결 G4 | 다익스트라(BFS도 가능) 다익스트라 유형으로 되어있지만 BFS도 가능한거 같다. BFS로 풀 면 길을 찾아 갈 때 0이면 그냥 가고 1이면 +1해서 가면 된다. 이 문제는 다익스트라로 풀어봤다. ( 다익스트라와 우선순위큐(힙큐)는 짝꿍 ) 주어진 미로와 같은 크기의 2차원 배열을 만든다. ( 가중치를 업데이트 해줄 배열 ) 0,0 부터 주변을 탐색하며 방(0)이면 비용을 현재비용으로 넣고, 벽(1)이면 비용을 현재비용 +1해서 업데이트 해준다. 업데이트가 된 지점을들 힙큐에 넣고 목적지가 나올 때 까지 위의 과정을 반복한다. 💻소스 코드 import heapq if __name__ == '__main__': N, M = map(int, input().split()) # 문제는 1부..

[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 ..

[javascript] 프로그래머스 - 단어 변환

🤔문제 해결 Lv3 | BFS begin 에서 시작하여 BFS 탐색 BFS는 target과의 거리를 알 수 있으므로 target과의 최단거리를 구해서 답을 출력 아래의 코드에서는 visited와 words_obj를 사용했지만 잘 짜보면 words_obj 하나로 충분히 구현할 수 있다! 💻소스 코드 function solution(begin, target, words) { var answer = 0; // 타겟이 워드에 없는 경우 if (!words.includes(target)) { return answer } let n = words.length // visited 와 queue let visited = Array(n).fill(0) let q = [begin] // 단어의 인덱스를 객체에 저장 con..

[python] 백준 - 7562. 나이트의 이동

🤔문제 해결 S2 | BFS BFS로 다 돌아주다가 도착지를 만나면 끝! 💻소스 코드 from collections import deque def bfs(): q = deque() q.append((start_x, start_y)) while q: cx, cy = q.popleft() if cx == end_x and cy == end_y: print(chess[cx][cy]) return for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

너비 우선 탐색(Breath First Search, BFS)

📔 너비 우선 탐색(BFS) 이란 너비를 우선으로 하여 탐색을 수행하는 알고리즘 최단경로(최단길이)를 찾을 때 주로 사용한다. 큐와 그래프로 해결한다. (파이썬에서는 데크(deque)를 쓰면 속도가 빠름) 📔 너비 우선 탐색(BFS) 구현 from collections import deque # 인접리스트 # 노드: 1,2,3,4,5,6,7 n = 7 adj = {x: [] for x in range(1, n + 1)} edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ] # 무방향 그래프이므로 반대쪽도 성립 for edge in edges: s, e = edge adj[s].append(e) adj[e].append(s) print(adj) # bfs..

[python] 백준 - 5014. 스타트링크

🤔문제 해결 G5 | BFS, 그래프 갈 수 있는 길이 2가지인 BFS 문제. 한 지점에서 올라가거나 내려가거나 하면서 원하는 층에 도착할 수 있는지 판별한다. 최초 시작점 S에서 올라가거나(U) 내려간다(D) 만약 올라갈 때 건물의 높이보다 높으면 못올라가고, 내려갈 때 1층보다 낮으면 못내려간다. 또 visited리스트를 만들어둬서 이미 방문했었는지 보고 방문을 안했던 층만 방문한다. BFS로 하기 때문에 이미 방문한 층에 한번 더 들르면 큰값이 들어가게 되므로 무조건 손해이다. 계속 방문을 하면서 원하는 지점(G)에 도착한다면 그 값을 리턴해주고, 도착하지 못한다면 'use the stairs' 를 리턴해준다. 💨 💻소스 코드 from collections import deque def bfs():..