본문 바로가기

BFS68

[자바] 백준 23817 - 포항항 (boj java) 문제 : boj23817 상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다. 로직을 나눠서 생각해보자. 1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다. -> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 .. 2022. 6. 25.
[자바] 백준 6755 - Who is taller? (boj java) 문제 : boj6755 입력으로 들어온 M개의 x가 y보다 크다는 정보를 가지고, p가 q보다 큰지(yes) 혹은 q가 p보다 큰지(no) 혹은 검증이 불가한지(unknown) 알아낼 수 있어야 한다. 그래프로 생각해보자. 우선 각 N명의 사람을 정점으로 하고, 간선을 x에서 y로 (즉 큰 사람에서 작은사람쪽으로) 하는 방향 그래프를 생각해보자. 그럼 간단히 p에서 q로 간선을 타고 이동이 가능하다면 p가 q보다 큰게 된다. 반대로 q에서 p로 간선을 타고 이동이 가능하다면 q가 p보다 큰게 된다. 둘 다 불가했다면 검증이 불가하다. 지문의 'you always compare correctly'에 따라 사이클이 생긴다거나, p에서 q로도 갈 수 있고 q에서 p로도 갈 수 있는 상황은 그냥 문제가 틀린셈이.. 2022. 6. 25.
[자바] 백준 24513 - 좀비 바이러스 (boj java) 문제 : boj24513 문제를 풀 개념만 확실히 잡는다면, 그 이후로는 구현력에 달려 있는 문제이다. 구현이 상당히 복잡할 수 있다. 구현자체는 코드를 참고해서 짜보고, 일단 개념만 풀이로 작성해보겠다. 이하의 예시를 생각해보자. 3 3 1 0 0 0 0 0 0 0 2 우선 1번 바이러스가 전체 맵을 진행할 때, 각 마을에 도착하는 시간을 재보면 다음과 같을 것이다. 그 다음 2번 바이러스가 차례차례 1번 바이러스의 지점들을 덮으면서 진행해보자. 위에서 동일한 거리끼리 만나게 되었다. 즉, 해당 지점에 각 바이러스는 동일한 시각에 도착한다는 의미이다. 따라서 이 지점에서 3번 바이러스가 만들어지게 되는 것이다. 최종적으로 각 마을마다 감염되는 바이러스의 번호는 다음과 같다. -------------- .. 2022. 6. 8.
[자바] 백준 18818 - Iguana Instructions (boj java) 문제 : boj18818 bfs로 진행하되, 거리가 증가되는 기준이 한 방향으로 일직선으로 장애물을 만나기 전까지 모두가 동일한 거리를 가진다.그리고, 한 방향으로 일직선으로 진행하면서 만난 모든 지점을 큐에 추가하면서 풀어주면 된다. 예를들어 예제 입력 2를 봐보자. 5 ..... .###. ..... .#### ..... 우선 시작점에서 bfs를 진행한 결과에 따른 각 지점의 거리는 다음과 같다. 그리고 현재 거리가 '1'인 지점은 모두 큐에 추가된 상태이다. 맨 윗줄만 봤을 때, 2,3,4번째 칸들은 더이상 진행할 곳이 없으므로 그대로 무시된다. 맨 윗줄 5번째칸에서 진행한 결과는 다음과 같을 것이다. 다음으로 좌측줄 정중앙에서 진행한 결과는 다음과 같다. 마지막으로 맨 아래줄 좌측에서 진행한 결과.. 2022. 6. 8.
[자바] 백준 24445 - 알고리즘 수업 - 너비 우선 탐색 2 (boj java) 문제 : boj24445 bfs가 뭔지 모른다면 이 글을 참고해보자. 일반적인 bfs 구현인데, 문제는 다음 정점을 내림차순으로 선택해야 한다. 그리고 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 된다. 그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { int[] answer; ArrayList[] edges; int idx = 0; int[] v; private .. 2022. 6. 4.
[자바] 백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (boj java) 문제 : boj24444 일단 bfs가 뭔지 모른다면 이 글을 참고해보자. 일반적인 bfs 구현인데, 문제는 다음 정점을 오름차순으로 선택해야 한다. 그리고 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 된다. 그러니 인접 리스트로 간선을 표현하자. 이 때 오름차순으로 다음 정점을 선택해야 하므로, 미리 아름차순으로 각 정점의 간선들을 정렬시켜두면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { int[] answer; ArrayList[] edges; int idx = 0; int[] v; priva.. 2022. 6. 3.
[자바] 백준 1897 - 토달기 (boj java) 문제 : boj1897 문제에서 제시된 로직대로 진행한다면, 항상 L 길이의 단어는 L+1 길이의 단어가 된다. 또한 이 때, L 길이의 단어에 있는 각 문자의 순서는 L+1 길이의 단어에서 나타나는 문자의 순서와 동일하면서, 딱 하나의 문자만 추가될 것이다. 그렇다면 현재 L길이의 단어를 보고 있을 때, L+1 길이의 단어들 중 이동 가능한 문자로 진행을 하는걸 더이상 진행할 수 없을때까지 해보면 될 것이다. 즉, 그렇게 안생겼지만 bfs나 dfs로 풀면 된다. 간선은 [L 길이의 문자 A] -> [A와 문자 순서까지 생각했을 때, 1개의 문자만 추가된 문자 B] 와 같이 생성하면 될 것이다. 미리 입력을 받으면서 글자의 길이에 따라 나누어두면 훨씬 효율적으로 진행할 수 있다. 또한 String이므로 .. 2022. 5. 20.
[자바] 백준 25195 - YES or yes (boj java) 문제 : boj25195 그래프 탐색에 대해 단순하게 DFS, BFS만 익힌게 아니고 이해하고 있다면 사실 엄청 쉬운 문제이다. 결국 DFS(깊이 우선 탐색)으로 진행하면서 팬을 만나지 않고 더이상 진행할 간선이 없는 곳에 도착하는지만 보면 된다. 주의할 점은 방문체크를 두면 안된다. 왜냐면 이미 팬을 만난채로 진행한 경로라서 방문체크가 됬더라도 팬을 만나지 않은채로 진행이 가능해야 하기 때문이다. 이럼 사실 방문체크를 하되, 팬을 만나고 도착했는지 팬을 안만나고 도착했는지에 따라 dp를 좀 끼얹어서 그래프 탐색을 해도 되긴한다. 근데 어차피 DAG(Directed Acyclic Graph. 사이클 없는 방향그래프)이므로 팬을 만났다면 바로 back tracking으로 이전으로 돌아가기만 해도 된다. 이.. 2022. 5. 16.
[자바] 백준 8244 - Tales of seafaring (boj java) 문제 : boj8244 자바로는 정신건강상 시도 안하는걸 추천한다. 자바론 사실상 통과 불가능한 메모리 제한이라 메모리 초과를 뚫기 위해 이상한 짓들을 많이 해야 한다. 1. 키 아이디어 기본 아이디어는 어찌보면 생각하기 어렵고 어찌보면 간단한데 다음의 그래프를 보자. 이 때 k개로 주어진 각각의 'tales that Bytensson has heard'중 하나를 Q라고 칭하겠다. 이 때 1에서 출발해서 2로 가는 최단길이는 1이다. 그럼 Q가 '1 2 1'이라면 당연히 가능하다. 그럼 '1 2 3'이나 '1 2 5'라도 가능할까? 이것도 가능하다. 왜냐면 한 번 들렸던 곳을 다시 못간다는 제한이 없으므로 다음과 같이 왔다갔다 하면 되기 때문이다. 최단거리는 1이지만, 그 이후로 1+2*n (n은 0부터.. 2022. 4. 30.
백준 20420 자바 - 화살표 미로 (Normal) (BOJ 20420 JAVA) 문제 : boj20420 매운맛의 BFS 문제였다. BFS에 대해서는 여기에 작성해놨다. 해당 글의 내용만 있으면 풀 수 있는 문제이다. 이 문제를 풀 수 있는 BFS 적용 아이디어를 작성해보겠다. A. BFS 진행 시 인접한 곳은 원래 주어진 방향, 좌측으로 회전해서 갈 수 있는 만큼의 방향(예를들어 남은 L이 2라면 좌측으로 2번까지 돌 수 있다.), 우측으로 회전해서 갈 수 있는 만큼의 방향 이다. B. 좌측으로 4번 혹은 우측으로 4번을 돌면 원래 방향이 되므로 무조건 손해이다. 따라서 좌측으로 3번, 우측으로 3번까지만 확인해야 한다. 이 때, 예를들어 좌측으로 3번이 우측으로 1번과 동일하다고 해서 2번까지만 확인하면 안된다. 남은 횟수가 한쪽이 더 많을 수도 있다. C. 방문체크는 모든 경우.. 2022. 3. 25.

티스토리툴바