밤이 블로그

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#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..

BOJ#1987 알파벳 (Letters) * 문제https://www.acmicpc.net/problem/1987 * 풀이알파벳이 중복되는지 판단하는 방법으로 2가지 방법을 사용해 보았습니다.(비트마스크, 길이가 26인 boolean visited 배열) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231987_Alphabet/src import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1987 알파벳 * https://www.acmicpc.net/proble..

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#5014 스타트링크 * 문제https://www.acmicpc.net/problem/5014 * 풀이 생략 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%235014_Startlink/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; /** * BOJ#5014 스타트링크 * https://www.acmicpc.net/problem/5014 *..

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