J

풀이 BFS로 문제 풀이를 할때 투포인터를 활용하는 문제이다. 투포인터를 이용하여 가장 높은 고도와 가장 낮은 고도를 지정하여 그 사이에서만 BFS를 하도록 할 것이다. isDelivery 함수를 통해서 정해진 고도 내에서 방문할 수 있는 집의 개수를 반환한다. 방문해야 하는 집의 개수와 방문할 수 있는 집의 개수가 같다면 고도의 차이를 줄이기 위해서 low를 가리키고 있는 minIndex의 값을 증가시킨다. 만약 방문할 수 있는 집의 개수가 더 작다면 high를 가리키고 있는 maxIndex의 값을 증가시킨다. 전체 코드 import java.io.*; import java.util.*; public class Main { static int N; static char[][] map; static in..

풀이 방법 PriorityQueue를 사용하여 String이 사전 순으로 계속 정렬되게 한다. 가지치기를 하면서 poll 값을 조사할지 말지 결정한다. 도착 위치와 현재 위치 거리가 남은 거리보다 크면 절대 도착할 수 없다. (현재 위치와 도착 위치 사이 거리)와 남은 거리의 홀짝은 같아야 한다. import java.io.*; import java.util.*; class Solution { static class load{ int x; int y; int time; String route; load(int x, int y, int time, String route){ this.x = x; this.y = y; this.time = time; this.route = route; } public Stri..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 💡 부분집합과 BFS를 활용하여 문제를 해결하였다. 1. 부분 집합을 통해 5X5 좌표에서 7개를 골라준다. 2. 이때 'Y'의 개수가 3개이상이면 return 해준다. 3. 7개를 골라주면 BFS를 통해 서로 연결되어 있는지 확인해준다. 전체 코드 import java.util.*; import java.io.*; public class Main { static char[][] classroom; ..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 비트마스킹과 BFS를 활용해야 하는 문제이다. 1. visited를 3차원 배열로 선언하여 현재 x, y와 key의 상태를 가지고 방문했는지를 판단해준다. 2. 다음 위치가 key인 경우 가지고 있는 key정보를 갱신한다. 3. 다음 위치가 문인 경우 현재 key 중 문을 열 수 있는 경우 열어준다. 4. 빈 공간인 경우 원래처럼 visited만 갱신한다. 5. 전부..