밤이 블로그

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#12930 두 가중치 * 문제https://www.acmicpc.net/problem/12930 * 풀이최단거리 다익스트라 알고리즘으로 풀어봅시다.개념만 충실히 알고 계시다면 어렵지 않게 풀수 있을듯 합니다. 따라서 풀이 설명은 생략합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/71d4c79293704f4539e025b72a7470964685156c/BOJ%2312930_Weights/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Pri..

BOJ#1937 욕심쟁이 판다 * 문제https://www.acmicpc.net/problem/1937 * 풀이dp + 탐색 * 나의 코드https://github.com/stack07142/BOJ/blob/9fb5631acdf38f48b28e2ee02bc0ac4a6a4c3a7f/BOJ%231937_GreedyPanda/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1937 욕심쟁이 판다 * https://www.acmicpc.net/problem/1937 */ public class..

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#1854 K번째 최단경로 찾기 * 문제https://www.acmicpc.net/problem/1854 * 풀이아이디어 자체는 간단합니다.다익스트라 알고리즘에서 버려지는 거리값들을 버리지 않고 K개 모아두면 됩니다.(최단 거리 값이 아니여서 Relaxation에 쓰이지 않는 값들, 혹은 최단 거리 값으로 교체되어지는 값들) http://docs.oracle.com/javase/8/docs/api/ PriorityQueuepublic PriorityQueue(int initialCapacity, Comparator

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...

BOJ#2667 단지번호붙이기 * 문제https://www.acmicpc.net/problem/2667 * 풀이dfs난이도 : 하 추천 문제 (2667번 다음에 풀어보면 좋을 문제) : 2146번 - 다리 만들기 https://www.acmicpc.net/problem/2146 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232667_Numbering/src/Main.java import java.io.*; import java.util.ArrayList; import java.util.Collections; /** * BOJ#2667 단지번호붙이기 * https://www.acmicpc.net/problem/2667 */ public class..

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.*; /** *..