[프로그래머스] 가장 먼 노드 (javascript, bfs)
Posted by 해랑쓰 블로그 (Haerang's blog)
연결리스트를 만들어준 다음 bfs를 돌면서 각 단계의 큐의 개수로 answer를 업데이트해줬다. (각 단계의 노드 개수) function solution(n, edge) { const list={}; for(let i=0;i
연결리스트를 만들어준 다음 bfs를 돌면서 각 단계의 큐의 개수로 answer를 업데이트해줬다. (각 단계의 노드 개수) function solution(n, edge) { const list={}; for(let i=0;i
www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 www.acmicpc.net 각 학생의 추천횟수를 저장하는 배열을 따로 만들어주고 정렬을 위한 학생 객체는 리스트로 만들어줘서 추가, 삭제가 용이하도록 하였다. package algo0419; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Student implements Comparable{ int num; int tot..
www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 말이 4개 이상 겹치면 탈출 chips라는 이차원 배열에 arraylist가 들어가게 해서 해당 위치에 칩 리스트를 만들어줬다. package algo0419; import java.util.ArrayList; import java.util.Scanner; class Horse{ int y,x,dir; public Horse(int y, int x, int dir) { super(); this.y = y; ..
nCr = n! / r!(n-r)! 이다. 페르마의 정리는 A ^ (P-1) = 1이다. A ^ (P-2) = 1/A = A ^(-1) A = ( r!(n-r)! ) P= 문제에서 주어진수 = 1234567891 외우지 않으면 모르겠다.. package algo0419; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class S_5607_조합_Solution { static int t,n,r; static final long MOD=1234567891; static long[] fact; public static..
상하 와 좌우를 번갈아 이동해야된다. visited 배열을 3차원으로 사용했다. 마지막은 인덱스는 가로, 세로 중 어디로 이동했냐를 가르킨다. 테스트케이스 45개만 통과되는 경우 시작점 = 도착점으로 주어져서 답이 0인 것을 처리해주지 않아서 그렇다. 예외로 0을 출력하도록 구현하면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int x,y,dir; public Pos(int x,int y,int dir) { super(); this.x = x; this.y = y; this.dir=dir; } } public class Solution { static int t; static in..
www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 구현인데 어려웠다 괄호가 코딩테스트에 자주 나오는 이유 ~ 중첩된 것의 계산을 어떻게 해줄지 떠올리느냐 아니냐가 중요했다 나의 경우 괄호의 깊이를 계산해서 후위계산식으로 만들어서 계산해줄려고 했는데 너무 길고 복잡해서 다른 사람 풀이를 참고 했다. --- 중첩되어서 안쪽에 있는 괄호쌍은 앞에서 곱해온 수에 현재 괄호쌍의 값을 곱한다. 여는 괄호에서 곱해주면 된다. ( 열 때마다 중첩되서 깊어지므로) 만약 현재..
www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 처음에 네트워크를 구하는 줄알고 dfs인 줄 알았으나 depth (친구의 친구)가 2인 곳까지만 탐색하므로 bfs로 풀었다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n,m; static ArrayList[]..
www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Main { static int n,m; static int[][] map; static in..
www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 미친 구현.. ㅎㅎ 옅은 영역과 보드가 모두 차는 경우 점수 계산 먼저하고 옅은 영역을 처리해준다. 이때 행을 밀게 되는데 옅은 영역번호 0,1 행 혹은 열에 해당하는 곳을 꼭 0으로 초기화해줘야된다. 점수를 계산할 때도 옅은 영역을 포함해서 밀어주되, 행 혹은 열이 0인 곳은 덮어씌워지지않으므로 꼭 0으로 초기화를 해줘야 된다. 나머지는 구현구현 import java.util.Scanner; pub..
www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 상어 주의할 점 사방에 냄새가 있을 경우 자기의 냄새 방향으로 간다. (자기의 냄새도 사방에 있을 수 있다. 여기서도 우선순위대로 처리해주자.) import java.util.Scanner; class Place{ int y,x; public Place(int y, int x) { super(); this.y = y; this.x = x; } } public clas..