DS & Algorithm/baekjoon

[백준] 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, 미방문..

[백준] 1932번 정수삼각형 - JavaScript(NodeJS)

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 다음 삼각형에서 꼭대기에서 아래로 내려오면서, 대각선으로 이동한다. 선택한 수의 합이 최대일 때를 구하면 된다. 삼각형의 크기 N은 (1 0->0 인덱스를 거쳐가므로 1개의 경우의 수만 존재한다. dp[N-1][N-1]의 값은 0->1->2->3...의 각 행의 마지막 인덱스를 거쳐가므로 1개의 경우의 수만 존재한다. dp[N-1][K]의 값은 K를 도착한 모든 경우의 수 중 가장 큰 값을 구하면 된다. K 인덱스 위치에 도착할 수 있는 방법은 이전 층(N-2 층)의 K..

[백준] 1309번 동물원 - JavasScript(NodeJS)

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 DP(동적 계획법) 문제이므로 DP로 접근한다. 다음 N * 2 행렬의 N번째 행만을 기준으로 생각하자. N번째 행에 사자가 없다면 E, 사자가 있다면 I로 나타내본다. N=1일 때, 경우의 수는 E=1, I=2 로 총 3이다. N=2일 때, N=1의 경우의 수 각각에 2번째 행이 생성되었을 때를 생각하면 E=1로부터 E=1, I=2 생성 I=2로부터 각각 E=1, I=1이 생성되므로 총 E=2, I=2가 생성 그러므로 N=2의 경우의 수는 E=1+2, I=2+2로 총 7이다. 계속해서 진행하면, N=3일 때, N=2의 경우의 수 각각에 3번째 행이 생성되므로 E=3으로부터 E=3, ..