밤이 블로그

BOJ#2931 가스관 * 문제https://www.acmicpc.net/problem/2931 * 풀이이 문제는 어려운 문제인지, 쉬운 문제인지 헷갈리네요. - 삭제된 노드는 단 1개이고 쉽게 찾을 수 있다. (출발점에서 파이프를 따라가보면 삭제된 노드가 나온다)- 위치는 구했고 거기에 맞는 파이프만 찾으면 되는데 노드에서 출입구가 몇개이고 어느 방향으로 뚫려있는지만 알면? 파이프를 구할 수 있다. 쉽다고 생각하면 쉬운데,,,정형화된(?) bfs, dfs 탐색으로는 어떻게 풀까? 문제 의도는 뭘까 아무튼 bfs, dfs 몰라도 자기 생각을 코드로 옮길 수 있으면 이 문제는 쉽게 풀 수 있을 것 같습니다.입사 시험에 적당한 문제 ↓ 테스트 케이스 보기 (클릭) ↓4 4Z...|...|....--M 4 1..

BOJ#2638 치즈 * 문제https://www.acmicpc.net/problem/2638 * 풀이가장자리에는 친절하게도 치즈가 존재하지 않으므로가장자리에서 dfs 탐색을 하면 외부 공기 지역을 구별해낼 수 있습니다. 1. 외부 공기 탐색(dfs)2. 모든 치즈에 대해 외부 공기 접촉 판단3. 접촉 시 치즈 없애기4. 1~3 반복....(치즈가 모두 없어질때까지) 주의할 점으로는...치즈를 즉시 외부 공기로 바꾸면 주변 치즈에 영향을 주게 되어 정확한 답을 구할 수 없습니다. 개선할 점으로는...step마다 dfs 탐색을 한번씩 수행하는 부분을 없앨 수 있겠습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/c6b101df6246e4a5c45c00a905ca92..

BOJ#10875 뱀 * 문제https://www.acmicpc.net/problem/10875 * 풀이 ※ 문제 풀 때 주의할 점 주어진 입력의 크기를 잘 살펴봅시다. L 7 TestCase #2332 L4 L4 R => 6 TestCase #3332 R1 R10 R = 9 TestCase #4332 R10 L4 R = 6 TestCase #5332 L10 L4 R = 6 TestCase #63310 L4 L4 R = 4 TestCase #7332 L4 L4 R = 6 TestCase #8342 L2 L1 L5 R = 7 TestCase #9342 R2 R1 R5 L = 7 TestCase #10352 R3 L1 L2 L10 L = 9 TestCase #11352 R3 R1 R2 R10 L = 9 Te..

BOJ#13911 집 구하기 * 문제https://www.acmicpc.net/problem/13911 University > 서강대학교 > 제 12회 총장배 서강대학교 프로그래밍 대회 Master F번 * 풀이매우 매우 추천하는 문제입니다. - 처음 생각한 알고리즘 1. 맥도날드 지점별로 다익스트라2. 스타벅스 지점별로 다익스트라3. 조건 만족하는 것 찾아내기 문제를 본격적으로 풀어보려는데,, 뭔가 찜찜합니다.입력값 범위가 심상치 않아 문제를 풀기전에 시간복잡도를 계산해봅니다. V ≤ 10,000, E ≤ 300,000 맥도날드 다익스트라 (V-2)번 : O(E*log(V)) * V-2번스타벅스 다익스트라 (V-2)번 : O(E*log(V)) * V-2번조건 만족하는 것 찾아내기 : ?? 결론 : 시간..

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