BFS

프로그래머스: 숫자 변환하기(javascript, deque, bfs)

BFS를 이용해 푼 문제이다. 처음에 BFS로만 풀려 했으나 계속 시간초과가 나서 백준 소꿉놀이처럼 미리 배열을 선언해두고, 시작점을 1로 해둔다. 그리고 방문안한 점을 방문할 때만 이전 지점에 1을 더해서 연산 횟수를 기록하는 방식이다. 글까지 써가며 기록하게 된 이유는 자바스크립트의 배열은 shift와 unshift연산이 모두 되는 deque이기에 bfs를 쓸 때 그냥 배열에 저장했었는데 테스트 케이스 두개가 계속 시간초과가 나서 자료구조를 다른 사람이 구현해놓은 deque을 사용했는데 훨씬 빠르게 통과돼서 놀랐었다. 왜냐하면 보통 내장함수나 내장 자료구조보다 잘 구현하기는 힘들기 때문이다. 앞으로 deque이나 queue자료구조가 필요한 알고리즘 문제는 자료구조를 직접 구현해서 써야겠다. class..

백준 13913번: 숨바꼭질4 (javascript, BFS)

숨바꼭질 문제의 변형판이다. 최단경로와 그 경로를 출력해야 한다. 최단경로는 이전에 구한 것처럼 BFS를 이용해 구할 수 있다. 새로운 배열을 선언하고 방문한 점의 위치에 이전 점의 위치를 저장하고, 목표 위치인 K에 도착했을 때 반복문으로 이전 좌표들을 따라감으로써 방문경로를 확인하였다. 코드는 다음과 같다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a)) function BFS(x, k){ let queue = [x] let array = new Array(MAX).fill(0) let path = new Array(MAX).fill(0) ..

백준 1697번: 숨바꼭질 (javascript, bfs)

쉬운 문제이나 또 어려운 문제였다. 시간제한도 넉넉하고 문제도 쉬우나 그 시간제한을 맞추게 알고리즘을 짜는게 쉽지 않았다. 가장 빠른 시간, 즉 최소를 묻는 경우는 보통 풀이 알고리즘이 그리디, DP, BFS가 있다. 그 중에 BFS를 이용해 풀었는데 왜냐하면 수빈이가 이동할 수 있는 경우의 수가 3가지로 정해져 있기 때문이다. 처음 푼 풀이는 visited 집합과 queue를 동시에 사용해서 그 점에 방문한 적이 없으면 queue에 넣는 식으로 풀이를 짰다. BFS이므로 queue에 현재 위치와 움직인 시간을 동시에 넣어서 움직인 시간을 계산하고자 했다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().tri..

백준 16234번: 인구이동(javascript, BFS, 완전탐색)

완전탐색이며 BFS로 풀 수 있는 문제이다. 물론 DFS로도 풀어도 되지만 문제 조건에 인접한 국가만 국경을 열 수 있다는 점에서 넓이 우선 탐색이 좀 더 직관적으로 풀 수 있다고 생각해 BFS로 접근하여 풀었다. 예제에서 N이 3이상인, 즉 인구이동이 다른 구역에서 동시에 일어날 때 인구가 어떻게 합쳐지는 지에 대한 설명이 없어 디버깅에 조금 어려움을 겪었던 문제였다. 물론 예제 4,5를 통해 알수는 있지만 그 과정을 일일히 찾기에 어려움이 있었다. 예제 4,5에서 인구이동이 일어나는 과정을 적은 글이 있어 이 문제를 푸는데 어려움을 겪는 사람이 있다면 참고하면 디버깅에 도움이 될 것 같다. const fs = require('fs'); const input = fs.readFileSync("/dev/..

백준 2589번: 보물섬(javscript, BFS, 완전탐색)

전형적인 BFS이며 브루탈 포스(완전탐색) 문제이다. 문제에서 보물이 묻혀있는 곳 두 거리간의 최단거리를 요구하고 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 최단거리로 이동할 수 있는 방법은 BFS 알고리즘이다. 왜 BFS알고리즘이 최단거리인지는 트리를 어떻게 탐색하는 지를 생각해보면 쉽게 이해할 수 있다. 따라서 이 문제는 완전탐색을 통해 BFS로 육지마다 다른 육지들로 이동할 때의 거리들 중 최대거리를 구하면 그 값이 답이 된다. 또한 BFS는 DFS와 다르게 한번의 이동에 주변을 다 탐색하므로 이동할 때마다 이동거리를 증가시키면 안되고 이전 이동거리에 1을 더해서 이동거리를 계산해야 한다. 위 생각을 토대로 짠 코드는 다음과 같다. 주의할 ..

프로그래머스: 가장 먼 노드(파이썬, BFS)

그래프의 root node로부터 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. 문제의 조건에서 가장 멀리 떨어진 노드의 정의에 대하여 최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드라 명시하였다. 그래프의 탐색이기에 우선 그래프를 인접 행렬로 표현하였고 그 다음으로 그래프의 탐색방법인 DFS, BFS중 고민하였는데 BFS로 푸는 것이 더 효율적이라는 생각이 들었다. 왜냐하면 DFS는 모든 경로를 전부 탐색하여 비교하기에 BFS보다 시간복잡도측에서 비효율적이기 때문이다. 일반적으로 그래프를 탐색하거나 간선들의 가중치가 모두 같을 때 최단경로를 구한다면 BFS가 효율적이다. 혹은 DP를 쓰던지.. 따라서 BFS로 문제를 풀었다. 기본적인 BFS 구현 코드를 사용하였고 거기에 queue에 자식 노..

프로그래머스: 단어 변환 (파이썬, BFS)

변환 횟수가 최소인 경우를 구해야 하므로 BFS로 접근하였다. 처음에 단어들을 어떻게 그래프로 표현할까 하다가 변환 경우의 수를 그려보니 굳이 그래프로 표현 안해도 풀 수 있다는 생각이 들었다. 처음에 테스트케이스3에서 계속 틀렸었는데 그 이유는 두 단어간에 다른 알파벳 갯수를 셀 때 set을 이용해 세었기 때문이다. 그럼 'ccec'같은 단어는 'ce'가 되므로 적절한 비교가 이루어지지 않음을 알 수 있다. 아직 엣지케이스를 생각하는 능력이 부족한 것 같아 그 부분에 대해 좀 더 훈련이 필요하겠다.. 풀이 코드는다음과 같다. BFS는 넓이를 우선으로 탐색하므로 처음에 begin과 차이가 1인 단어들을 deque에 넣고 그 단어들에 대해 다시 차이가 1인 단어들을 deque에 넣으면 넓이 우선 탐색으로 ..

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다. DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다. from copy import deepcopy import sys sys.setrecursion..