밤이 블로그

BOJ#1963 소수 경로 * 문제https://www.acmicpc.net/problem/1963 * 풀이- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수 (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능) - 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x - 예를 들어 Test Case가 '1033 8179'인 경우 step = 0;1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)....결국 step == n에서 8179를 찾게 ..

BOJ#11729 하노이 탑 이동 순서 * 문제https://www.acmicpc.net/problem/11729 * 풀이 처음에는 bfs + 비트마스크를 이용하여 풀었습니다.하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.) 그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로총 시간복잡도 3^22로 시간초과 발생합니다. , - 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식- 단점 : 보통 재귀 방식으로 구현되는데, 재..

BOJ#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..

BOJ#1600 말이 되고픈 원숭이 * 문제https://www.acmicpc.net/problem/1600 * 풀이bfs 탐색 문제입니다.일반적인 격자(상,하,좌,우) 문제에서 말처럼 이동하는 부분이 추가되었다고 생각하면 됩니다. 즉, 각 위치에서 상하좌우(4방향) + 말(8방향) 이렇게 12가지 방향으로 탐색을 진행하면 됩니다.문제는 중복된 정점을 다시 방문하지 않도록 처리하는 것입니다. 처음에 제가 실수했던 점은 discovered[row][col][말로 방문한 경우 or 원숭이로 방문한 경우] 로 중복된 정점을 처리했었는데 이것의 반례로 아래의 예가 있습니다. 15 50 1 1 0 10 0 1 0 10 0 0 1 10 1 0 1 01 1 0 1 0 정답 : 6 말의 움직임에 의해 (2,1)에 위치..

BOJ#1938 통나무 옮기기 * 문제https://www.acmicpc.net/problem/1938 * 풀이통나무의 길이가 항상 3이므로, 중심 위치만을 가지고 탐색을 해봅시다.상하좌우, 회전 5가지 경우의 bfs 탐색을 진행하면 되겠습니다. 정점 중복 방문 처리는 discovered[행][열][통나무 방향(세로 또는 가로)]으로 잡아봤습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/ca62ee46326ab3ef50a46f562b4783773e0e0551/BOJ%231938_MovingLogs/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

BOJ#2665 미로 만들기 * 문제https://www.acmicpc.net/problem/2665Olympiad > 한국정보올림피아드 > KOI 1997 > 고등부 2번 * 풀이쉬운 문제입니다. 20년 묵은 문제네요, 😅 왜 쉽냐면,검은 방을 흰색 방으로 바꾸는 개수의 제한도 없고, 바꿀 때 필요한 규칙도 없기 때문입니다. 그냥 이 문제는.. 다익스트라 돌리면 됩니다. 비슷한 문제 : 1261번 - 알고스팟 https://www.acmicpc.net/problem/12612206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 * 나의 코드 https://github.com/stack07142/BOJ/blob/431a2fe10059904f604d38bc137..

BOJ#1194 달이 차오른다, 가자. * 문제https://www.acmicpc.net/problem/1194 * 풀이bfs 탐색 문제입니다.같은 정점을 여러번 방문해야 하는데, 어떻게 방문 여부를 처리할 것인가를 생각해야 합니다. (처리하지 않으면 큐 폭발) 저는 아래와 같이 discovered 배열을 boolean[row][col][열쇠]로 구성하였습니다. 즉, 해당 위치 (row, col)에 동일한 key를 갖고 방문한 적이 있으면 다시 방문할 필요가 없다는 것입니다. key는 a부터 f까지 6개가 있으므로 비트마스크를 이용하면 6bit로 가지고 갖고 있는 key의 정보를 표현할 수 있습니다.(배열 사이즈는 여유있게 설정했습니다.) static boolean[][][] discovered = ne..

BOJ#5427 불 * 문제https://www.acmicpc.net/problem/5427 * 풀이큐를 2개 만든 후 불의 위치와 상근이의 위치를 큐에 각각 삽입합니다.step 하나당 불과 상근이가 한 level만 bfs 탐색할 수 있도록 구성합니다. 결과적으로 상근이가 탈출한 경우 step을 출력하고, 아닌 경우 IMPOSSIBLE을 출력합니다. - 비슷한 문제 : 3055번 탈출 http://stack07142.tistory.com/search/탈출 탈출과 비슷한 문제입니다. 탈출의 경우에는 입력값의 경우가 적어서 map을 3차원 배열(row, col, 시간)으로 만들었지만이 문제의 경우에는 입력값이 크기 때문에 맵은 2차원 배열로 유지하였습니다. 211 1@3 3.#.#@#.#.3 3....@....

BOJ#1726 로봇 * 문제https://www.acmicpc.net/problem/1726 * 풀이BFS 탐색 문제입니다. 어려운 개념이 필요하거나 그런건 아닌데 문제 조건이 조금 복잡합니다.얼마나 꼼꼼하게 빨리 풀수 있는지가 관건인 듯 합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231726_Robot/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; imp..

BOJ#7569 토마토 * 문제https://www.acmicpc.net/problem/7569 * 풀이bfs 탐색 과정에서 상, 하, 좌, 우 뿐만 아니라 위, 아래도 추가해야 하는 문제입니다. 비슷한 문제 : BOJ#7576 토마토 https://www.acmicpc.net/problem/7576 (초등부 문제가 고등부 문제보다 어렵다..왜일까요 ?.? ) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%237569_Tomato/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util...