밤이 블로그

BOJ#2589 보물섬 * 문제https://www.acmicpc.net/problem/2589 * 풀이 모든 육지를 대상으로 bfs 탐색을 각각 수행해주면 됩니다.주의할 점으로는 각 탐색 시 visited 배열을 초기화해줘야 합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232589_TreasureIsland/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTok..

BOJ#2146 다리 만들기 * 문제https://www.acmicpc.net/problem/2146 * 풀이1. dfs 섬 구분하기2. bfs 섬 간 최단 거리 구하기 문제 추천 (2146번을 풀기전에 보면 좋을 문제) :2667번 - 단지번호 붙이기 https://www.acmicpc.net/problem/2667(섬 개수를 세는 문제)* 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232146_MakeBridge/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** *..

BOJ#9376 탈옥 * 문제https://www.acmicpc.net/problem/9376ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번 * 풀이어려운 문제라고 생각합니다. 일단 맵을 상하좌우로 1칸씩 늘려줍니다. -> 이유 : 시도1 처럼 여러 시작점들을 어딘가에 저장해놓고 조사하는 것과, 외곽의 어느 한점을 시작점으로 잡고 조사하는 것은 차이가 없다.(문이 아니라면 cost가 없기 때문) 죄수 2명을 탈옥시키는 방법은 3가지가 있습니다. 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우 2) 죄수2가 죄수1을 데리고 바..

BOJ#14226 이모티콘 * 문제https://www.acmicpc.net/problem/14226 * 풀이 푸는데 고생했지만 재밌는 문제입니다.처음에는 1000개의 테스트케이스 중 11개만 틀렸는데, 원인을 찾기 쉽지 않았습니다. BFS 돌리면서 visited 배열로 정점을 중복 방문하지 않게 구현했는데, 이것이 실패 원인이었습니다. 왜냐하면 정점의 값이 같더라도 클립보드에 어떤 내용이 들어있는지에 따라 향후 탐색할 수 있는 정점이 달라지기 때문입니다. 따라서 visited 배열을 discovered 배열의 개념으로 바꾸고discovered 배열을 (기존)boolean[][] discovered = new boolean[정점] (변경)boolean[][] discovered = new boolean[..

BOJ#2468 안전 영역 * 문제https://www.acmicpc.net/problem/2468 * 풀이 비가 내리는 양을 증가시키면서 BFS 또는 DFS를 수행하면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232468_SafetyZone/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; /** * BOJ#2468 안전영역 * https:..

BOJ#2206 벽 부수고 이동하기 * 문제https://www.acmicpc.net/problem/2206 * 풀이 BFS 또는 다익스트라로 풀 수 있습니다.벽을 부수는 경우와 벽을 부수지 않는 경우를 나누어서 진행하면 됩니다. 비슷한 문제 : 도로포장, 알고스팟 * 나의 코드 https://github.com/stack07142/BOJ/tree/master/BOJ%232206_WallDestroy/src import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Strin..

BOJ#3055 탈출 * 문제https://www.acmicpc.net/problem/3055 * 풀이BFS로 풀었습니다.map을 3차원 배열로 만들었고(행, 열, 시간)물의 위치에서 bfs 탐색, 그 이후 고슴도치 위치에서 bfs탐색하여 탈출이 가능한지 판단하였습니다. 비슷한 문제 : 5427 불 https://www.acmicpc.net/problem/5427 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%233055_Escape/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

BOJ#5214 환승 * 문제https://www.acmicpc.net/problem/5214 * 풀이 하이퍼튜브는 M개만큼 있고, 각각의 하이퍼튜브는 K개의 노드를 연결하고 있다. -> 간선 정보가 여태까지 풀어본 문제와는 다르게 주어짐-> 간선 정보를 어떤 자료구조에 어떻게 담을지 고민-> 인접 행렬은 메모리 초과 (N 각 하이퍼튜브는 최대 1000개의 노드 정보를 담고 있으므로, 이것을 일일이 짝을 맞추어가며 간선 정보를 저장하기 쉽지 않다. 생각한 아이디어는 다음과 같다.각 하이퍼튜브에 연결된 노드 정보는 아래와 같고1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 각 하이퍼튜브에 속하는 노드에 임의의 더미 노드를 생성하여 연결시킨다.10 ↔ 1, 10 ↔ 2, 10 ↔ 311 ↔ 1, 11 ..

BOJ#12851 숨바꼭질 2 * 문제https://www.acmicpc.net/problem/12851 * 풀이 쉬운 문제인데 푸는데 고생을 좀 했습니다. 일단은 1697 숨바꼭질 문제와 동일한데..동생을 찾는 가장 빠른 시간을 출력하는 것과가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다. 헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다. 즉, 입력 데이터가 1 10일 때가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만방법으로 따지면 아래와 같이 2가지가 있습니다.1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2) 따라서 방법의 개수를 구하려면 큐에 ..

BOJ#2178 미로 탐색 * 문제https://www.acmicpc.net/problem/2178 * 풀이 bfs(Breadth First Search) 기본 문제입니다. 개념만 알면 풀 수 있는 문제이기 때문에설명은 생략하겠습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232178_MazeSearching/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringToke..