본문 바로가기

Java78

[JAVA] 백준 - 소수 경로 1963 ( BFS + 에라토스테네스의 체) www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 1000 에서 9999까지 미리 모든 소수를 체크해놓는 것이 좋다. 소수를 체크하는 알고리즘은 에라토스테네스의 체를 사용하여 소수를 체크한다. public static void makePrimeNumber(){ for(int i=2;i 2020. 10. 16.
[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] 프로그래머스 - 단체사진 찍기 ( 카카오 코드 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.

티스토리툴바