DS & Algorithm

[백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS)

문제 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 정답 코드만 보고 싶으신 분은 맨 아래 코드를 참고! 이전 문제였던 (Two Dots 문제)[https://gobae.tistory.com/35] 에서 힌트를 얻었다. 이 문제에서는 2번의 절차가 필요해 보였다. 사이클(순환선)에 해당하는 노드들을 구한다. 모든 노드들을 조회하면서, 사이클까지의 최단거리를 구한다. 대충 이해한 바로는, 1번 절차는 dfs 쓰고, 2번 절차는 bfs를 쓰면 해결이 될 듯 했다. 시간초과 이슈에 ..

[백준] 16929번 Two Dots - JavaScript(NodeJS)

문제 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 풀이 N x M 크기의 게임판에서 사이클을 발견하는 문제이다. 문제에서의 사이클은 아래의 그림과 같이 4개 이상의 점들을 연결했을 때, 선이 아닌 도형을 이루면 된다. 풀이의 흐름은 다음과 같다. dfs를 이용해보자. 1. 현재 위치로부터 동서남북 위치에 있는 노드로 이동이 가능한지를 판단한다. 2. 이동하려는 노드가 처음 출발한 노드와 색이 동일한지 판단한다. 3. 이동하려는 노드가 이미 방문한 곳인지 판단한다. 방문하지 않았다면? => 방문한다...

[백준] 7562번 나이트의 이동 - JavaScript(NodeJS)

문제 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 I x I 행렬에서, 나이트의 위치에서 목표 위치까지 얼마나 빨리 갈 수 있는지를 구하는 문제이다. 최단경로를 구하면 되므로 BFS를 사용해보자. 나이트가 이동 가능한 위치는 그림과 같다. 나이트가 동일한 위치를 두 번 방문하는 것은 다른 위치로 이동했다가 다시 돌아온 경우이므로, 이를 방지하기 위해 visit 행렬을 통해서 이전 위치로 되돌아가는 경우를 배제한다. 나이트는 총 8방향으로 이동할 수 있으므로, 나이트의 현재 위치를 기준으로 8개 방향의 ..

[백준] 7576번 토마토 - JavaScript(NodeJS)

문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 토마토가 익기 위한 조건은 인접한 익은 토마토가 있고 하루가 지났을 때이다. 처음에 상자에서 익은 토마토들의 좌표를 파악해야 한다. 익은 토마토들의 좌표를 기준으로 하루마다 동서남북으로 전염(?)된다고 생각하자. 모든 행렬의 좌표를 조회할 필요는 없다. BFS를 사용해보자. 중요한 점은 하루마다 전날 추가된 익은 토마토들의 주변을 모두 탐색해야 한다. 전날에 익은 토마토가 3개가 있다면, 그 3개의 주변을 모두 탐색한다. 탈출 조건으로..

[백준] 2178번 미로 -JavaScript(NodeJS)

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 사실 문제를 처음 보고서는, BFS 구현에 익숙하지 않아서 모든 방법을 조회해보고 최솟값을 뽑아내도 괜찮겠다는 생각으로 우선 DFS로 접근했다. 하지만 결국 시간초과 이슈로, BFS로 해결했다. 이 문제는 최단경로 문제에 해당하는데, BFS는 너비 우선 탐색으로, 특정 지점에 가장 빨리 도착한 경우를 구하기에 적절하다. BFS는 while문과 queue 자료구조를 사용하여 구현할 수 있다. 자바스크립트에서 queue 자료구조의 구현은 배열과 push, shift 메서드를 사용하면 된..

[백준] 13023번 ABCDE - JavaScript(NodeJS)

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 상당히 고생했던 문제이다. 이 문제는, A와 B가 친구, B와 C가 친구, C와 D가 친구, D와 E가 친구인 경우가 존재하는지 구하면 된다. 그림과 같이 특정 노드에서 시작해서, 중복되지 않는 노드로 4번 이동할 수 있다면 (총 5개의 노드를 방문하면) 된다. DFS를 이용할 것이며, 그래프의 연결관계 표현을 위해 인접행렬을 이용하자. 변수 소개 각 변수들은 아래에 작성한 코드를 참고하자. N, M : 문제의 조건인 사람의 수(N), 관계의 수(M) adjM : N * N 인접행렬 check : 방문한 노드를 재방문하지 않기 위한 배열. 방문시 1, 미방문..