dfs

문제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..

문제https://www.acmicpc.net/problem/15686 풀이이 문제는 완전탐색 문제이며 DFS를 이용해 풀이를 진행했다. 우선 지도에 있는 치킨집의 위치를 담고 있는 배열과 치킨집 위치 배열의 방문 여부를 표시할 배열을 생성한다.위 두 배열을 이용해 문제에서 제공하는 제한할 치킨집의 갯수의 수 만큼 DFS로 검증한다. 이후 각 집 위치에서 치킨집으로 부터의 거리를 측정 후 더해준다.  코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ')..

문제https://www.acmicpc.net/problem/15683 풀이이 문제는 완전 탐색으로 풀이하는 구현 문제이다. 감시 카메라는 정해진 방향으로만 감시가 가능하며 감시 구역이 겹치는 것은 가능하지만, 중복된 영역에서 개수 증가는 한개만 가능하다. 또한 카메라 칸은 감시가 불가능 하지만, 그 다음 칸으로의 감시는 가능하다. 이러한 조건만 잘 지키면 구현에 큰 어려움은 없었다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Numb..

문제https://www.acmicpc.net/problem/12100 풀이해당 문제는 DFS를 이용한 완전탐색을 구현해 시뮬레이션 문제를 풀었다.DFS를 이용한 이유는 각 깊이별로 4방향으로 이동할 모든 경우의 수를 계산해야 하기 때문이다. 이 문제에서 어려웠던 부분은 한 방향으로 이동하면 블럭이 합쳐지는 로직이였다.블럭은 이동 방향의 끝 부분부터 합쳐지며 합쳐지면 이동해 합쳐진 블럭은 없어지게끔 구현했다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split..

문제https://www.acmicpc.net/problem/14888 풀이해당 문제는 완전탐색 문제이며, 필자는 DFS와 DP를 이용해 풀이했다. 숫자의 순서는 바뀌면 안되기에 연산자를 DP 배열에 담아가며 연산을 검증을 진행했다. 이전에 풀었던 스타트와 링크 문제와 비슷한 흐름으로 해결할 수 있었다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number))const N = input.shift()[0];const toolNum =..

문제https://www.acmicpc.net/problem/14889 풀이이 문제는 완전탐색과 DFS를 이용해 팀원의 조합을 구한 뒤 각 팀원의 조합의 점수 총합을 구한 뒤 양 팀의 점수 차 중 최소 값을 구하는 문제이다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n')const N = +input.shift();let arr = input.map(e => e.split(' ').map(Number));let answer = Infinity;let visited = new Array(..