본문 바로가기

백준45

[JAVA] 백준 - 레이저 통신 6087 (BFS) (테스트케이스 제공) www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 시작점 부터 도착점 까지 BFS 로 최소 개수의 거울 수를 업데이트한다. 처음에는 DFS로 쉽게 풀 수있을 거 같았지만 100 * 100 배열을 돌리니까 stackoverflow 가 발생했다. BFS 로 최소 거울 수 를 업데이트 해야한다. # 풀이 1. 클래스 정의 static class Pair{ int x,y,dir,mirror; public Pair(int x, int y, int dir, in.. 2020. 10. 15.
[JAVA] 백준 - 아기상어 16236 (BFS) www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net # 풀이 (핵심 로직) 1. BFS 를 사용하여 현재 아기 상어 위치에서 먹을 수 있는 모든 먹이를 찾는다. 2. 가장 가까운 먹이를 찾고 거리가 같다면 왼쪽 위에 있는 먹이를 고른다. 2번을 구현하기 위해 편하게 Comparable 을 구현하여 Collections 의 정렬 함수를 사용하였지만 메모리도 줄이고 속도도 늘릴 수 있는 방법도 존재한다. 코드가 늘어나고 정렬함수를 사용하더라도 메모리 사용.. 2020. 10. 15.
[JAVA] 백준 - 탈출 (3055) - (BFS) www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제�� www.acmicpc.net "움직이는 미로 탈출" 과 똑같은 문제다. onejunu.tistory.com/98 [JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS) www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가 onejunu.tistory.com 2차.. 2020. 10. 15.
[JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS) www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 미로가 움직이기 때문에 현재 좌표의 상태에 미로가 추가 되어야 한다. 즉, 현재 상태를 기억하는 정보에 미로를 추가해야한다. int 배열로 정보를 만든다면 메모리가 많이 들겠지만 다행히도 boolean 배열로도 정보를 기억할 수 있다. 또한 미로 역시 8*8 로 크기가 크지 않기 때문에 충분히 미로에 대한 정보를 들고 다녀도 된다. # 풀이 1. 현재 위치가 도착지점인가? 1-1. 도착지점이면 ok .. 2020. 10. 14.
[JAVA] 백준 - 벽 부수고 이동하기3 - 16933(BFS) www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽을 몇개 부수는지 + 낮/밤 인지 까지 다양한 조건들이 들러붙은 BFS 문제다. 풀이의 앞서서 방문 체크를 한 배열에 대해 설명한다. ch[x][y][0~1][0~k] 3번째 차원의 의미는 0 이면 낮 / 1이면 밤이다. 4번째 차원의 의미는 0이면 0개의 벽을 부순 상태/ 1이면 1개의 벽을 부순 상태/ .../ k 이면 k개의 벽을 부순 상태 이다. ch[1][2][1].. 2020. 10. 14.
[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] 백준 - 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.

티스토리툴바