문제https://www.acmicpc.net/problem/14502 풀이이 문제는 BFS를 이용해 풀이했다. 바이러스가 확장되는 모습이 BFS의 인접한 노드를 모두 방문하는 로직과 비슷했기에 BFS를 이용했다. 하지만 벽을 세우는 로직은 DFS와 비슷하다. 모든 빈 공간 중 3 칸에 벽을 세우는 경우를 구현하는데에 DFS와 같은 모습을 갖는 3개의 for 반복문을 이용해 구현했다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Numb..
BFS
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이 문제는 이전에 풀었던 카카오 문제와 비슷하다. 2Level / 2018 KAKAO BLIND RECRUITMENT / [1차] 프렌즈4블록 문제 출처 링크 문제 설명 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니 58cjdcns99.tisto..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/159993# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이 문제는 최단 길이를 구하는 문제이기에 BFS가 적절하다 생각해 풀었다. 시작 지점과 레버, 출구 지점을 주어진 맵에서 구하고 문제를 풀이할 BFS 함수를 구현했다. BFS함수를 구현할 때 햇갈렸다고 느낀 부분이 값의 반환 시점이다. 어떤 방밥으로도 도달 하고자 하는 지점까지 갈 수 없을 때, -1을 반환해야하는데 이 -1을 반환하는 타이밍을 정하는 것이 햇갈렸다...
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이 문제는 특정 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있는 다익스트라 알고리즘을 이용하는 문제이다.(다스트라 알고리즘은 추후 정리할 것이다) 1번(특정 노드)에서 출발해 각 번호까지의 코스트를 적립해 주어진 제한 코스트를 넘지 않는 번호의 갯수를 구하는 문제인데, 이 문제에서 BFS와 우선순위 큐를 이용해 다익스트라 알고리즘을 구현했다. 순수 BFS는 가..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이문제는 모든 전력망(노드)를 돌며 경우를 따져야 하므로 DFS와 BFS를 사용해도 된다. 나는 BFS를 사용했다. BFS 함수는 큐에 방문할 노드, visited에 방문한 노드를 저장해 주고 모든 경우를 탐색한다. 내 생각으로는 BFS함수에 각 시작점과 제외점을 주고 시작점과 제외점이 끊어졌다는 것을 가정하고 시작점과 연결된 노드의 갯수를 구한다. 그리고 반복문으로 w..
1. 정의 우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자. DFS 깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다. DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다. BFS 너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다. 큐를 이용해 탐색을 관리한다. 2. 구분 방법 그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나? 우선 그 문제를 분석해봐야한다. 그래프 탐색에서 모든 정점을 방문하는가? DFS와 BFS 둘 다 가능하다. 경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가? 고로타면 DFS를 이용하는게 유리하다. 최단 경로, 최단 거리를 구해야 ..
