밤이 블로그

BOJ#14500 테트로미노 * 문제https://www.acmicpc.net/problem/14500 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출 문제입니다. 테트로미노에서 dfs로 탐색 가능한 블록이 있고, 탐색 불가능한 블록(ㅓ, ㅗ, ㅜ, ㅏ)이 있습니다.즉, dfs로 탐색 + (ㅓ,ㅗ,ㅜ,ㅏ)에 대해 탐색을 하면 답을 얻을 수 있습니다. (ㅓ,ㅗ,ㅜ,ㅏ) 탐색 아이디어는 다음과 같습니다. 현재 위치가 (row, col)일 때(row, col)값과 (row, col)에서 상,하,좌,우 4방향 값을 모두 더해줍니다. 그리고 4방향 값에서 최소 값을 다시 빼줍니다.= 현재 위치 값 + 4방향 sum - 4방향 값 중 최소값 즉 플러스 + 모양에서 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#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#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...

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