본문 바로가기

algorithm68

[JAVA] 백준(14442) - 벽 부수고 이동하기 2 (BFS) www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽을 최대 K 개 부술수 있다. 벽을 부수지 않은 경우 / 1개 부순 경우 / 2개 부순 경우 .... / K개 부순경우 경우를 나눠서 방문 체크를 하며 BFS 하면된다. 평범한 2차원 배열의 BFS라면 2차원 배열로 해당 위치를 방문 체크하면 되지만 경우를 나눠서 방문 체크하는 이유는 다음과 같다. 만약 ( x, y ) 라는 위치에 먼저 방문했다고 해서 최단거리임을 보증할 .. 2020. 10. 12.
[JAVA] 백준 - 돌그룹 12886 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net # 2개의 그룹의 돌 개수를 알면 나머지 한 그룹의 돌 개수는 자동으로 정해진다. 따라서 2차원 배열로 방문체크를 해도된다. 예를 들어, { 4, 5, 6 } 의 돌 그룹이 있다고 하자. 그러면 check[4][5] 만 하면된다. 반대로 check[5][6]을 했다면 check[4][5]는 필요없다. 또한 순서도 상관없다. check[4][5] 를 하거나 check[5][4]를 하거나 똑같다. 왜냐면 4,5.. 2020. 10. 11.
[JAVA] 백준 연구소 - 14502 ( BFS + DFS) www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net # 벽은 어디다가 설치하는가?? 반드시 3개만 설치해야한다고 조건에 명시되어 있다. 최대 배열의 너비가 8*8 = 64 이므로 여기서 3개를 선택하는 최대 모든 경우의 수는 41644 이다. 완전 탐색으로 3개를 선택해도 무리가 없다. 완전탐색이 가능하면 더이상 생각할 필요가 없는 듯하다. 벽 3개를 선택하는 로직은 DFS를 선택한다. static void dfs(int idx,int cnt){ if(idx == tota.. 2020. 10. 11.
[JAVA] 프로그래머스 - 단체사진 찍기 ( 카카오 코드 2017 본선 ) 문제를 처음에 잘못이해해서 왜 3648 가지가 나오는지 고민했는데 그냥 단순한 순열 문제였다. # 3648 인 이유 N 과 F 는 이웃하면서 R과 T 사이에 3명이상 사람이 오는 경우의 수를 묻는다. 1) R 과 T사이에 NF포함 3명이 있는 경우 = 4! * 4C1 * 2! * 2! * 2! = 768 2) R 과 T 사이에 NF를 포함하지 않는 3명이 있는 경우 = 3! * 4C3 * 3! * 2! * 2! = 576 3) R 과 T 사이에 NF 포함 4명이 있는 경우 = 3! * 4C2 * 3! * 2! * 2! = 864 4) R과 T사이에 NF를 포함하지 않는 4명이 있는 경우 = 2! * 4! * 2! * 2! = 192 5) R 과 T 사이에 5명 있는 경우 = 2! * 4C3 * 4! * .. 2020. 10. 9.
[JAVA] 백준 - DSLR 9019 ( BFS) www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 클래스 Pair 를 계속 생성해서 그런지 모르겠는데 메모리 엄청 쓴다.. 쓰지 않으면 더 빠르게 구동 되지만 직관적으로 이해하고 문제 풀이가 빨라서 Pair 클래스를 만들어서 쓰고 있다. # 문제의 관건인 D S L R 을 구현하기 //D nx = (x*2)%10000; //S nx = x==0?9999:x-1; //L nx = (x%1000)*10 + (x/1000); //R nx = (x/1.. 2020. 10. 8.
[JAVA] 백준 - 데스나이트 (BFS) www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 가장 기본적인 로직만 있는 문제. 상하좌우가 아니라 이동할 수 있는 다음 장소가 6군데라는점만 조심하면 된다. 또한 한번 방문한 곳을 또 방문하여 최단거리를 갱신하는 일은 없으므로 2차원 배열로 방문 체크를 해도된다. import java.util.LinkedList; import java.util.*; class Main{ stat.. 2020. 10. 8.
[JAVA] 백준 - 뱀과 사다리 게임 (BFS) www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀으로 가면 무조건 손해라고 생각했지만 아니다. 만약 아래처럼 테스트 케이스를 주어진다고 해보자. # 뱀을 타야만 최단거리를 만드는 테스트 케이스 2 1 2 50 49 100 51 48 1. 1을 던져서 2번으로 간 다음 사다리를 타고 50으로 간다. 2. 1을 던져서 51번으로 간 다음 뱀을 타고 48로 간다. 3. 1을 던져서 49번으로 간 다음 사다리를 타고 .. 2020. 10. 8.
[JAVA] 백준 구슬탈출 2 - 13460 ( DFS & 구현) www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구현 + dfs 문제 1. 빨간 구슬과 파란 구슬은 동시에 같은 위치에 있을 수 없다.(핵심구현) 구현의 첫번째 난관이다. 아래처럼 방향을 정하고 int[] dx = {-1,1,0,0}; int[] dy = {0,0,-1,1}; 기존 위치가 [x,y] 라면 다음 위치는 [ x + dx[i], y + dy[i] ] 이다. (이때 i는 0부터 3까지 중 하나의 숫자.. 2020. 10. 1.
[JAVA] 백준 최단 경로 1753 ( 다익스트라 알고리즘) www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 자바는 기본적으로 우선순위 큐는 최소힙으로 구현되어 있다. 알고리즘은 아래와 같다. 1. 다익스트라 알고리즘 준비물 : dist 배열 (출발점에서 각 지점까지 최단거리 배열 초기는 모든 값이 INF ) / visited 배열 / 인접리스트 or 인접행렬 등 그래프 간의 가중치를 알 수 있어야 함. 1. 우선순위큐 (최소힙) 생성 2. 출발 정점 dist는 0 으로 초기화 3. 큐에 출.. 2020. 9. 27.