박카스러버

https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 전형적인 DFS문제입니다. DFS에서 행이 n-1에 닿으면 true를 리턴하여 안쪽까지 침투할 수 있다는 것을 표시하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.fun..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 처음에는 방문체크를 하지 않고 진행하여 메모리 초과가 나왔습니다. visited배열을 통해 방문 체크를 하였습니다. 하지만 해당하는 경우의 수도 같이 출력해야하기 때문에 Queue에 넣을 때 visited를 true로 만들지 않고 queue에서 깨낼 때 visited를 true로 만들었습니다. 그리고 배열의 크기는 LIMIT의 2배까지 되게 만든 이유는 2배로..

https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 오랜만에 풀어서 생각을 제대로 하지 못했습니다. 처음에는 하나의 배열을 만들어 한 줄로 세우고 친구인지 검증하는 방법을 생각하였습니다. 하지만 이 방법은 중복되는 부분이 존재하기 때문에 이를 어떻게 처리해야할 지 고민하다가 책의 풀이를 봤습니다. 책을 풀이를 보니 배열을 만들 필요가 없었고 제가 생각한 풀이 방법은 중복되는 부분들을 어찌저찌 제거해도 비효율적으로..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 처음에는 모든 값을 받고 정렬하는 방법을 생각했습니다. 하지만 A, B의 값이 정렬되있다는 것을 보고 각각의 배열의 포인터를 통해 작은 값을 계속 출력하면 되겠다고 생각하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringT..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 전형적인 플루이드-워샬 문제이다. 플루이드-워샬의 실수하기 쉬운 부분은 중간 인덱스가 3중 for문 중 가장 밖에 있어야한다는 것이다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.function.Function;..

https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com dfs의 조건에 실수를 해서 오래걸렸습니다. 또한, StringBuilder를 통해 테스트 케이스가 너무 끝나고 출력해도 오답이 나온다. 바로바로 출력하거나 최소한 테스트 케이스마다 출력해야하는 것 같습니다. 저는 dp의 값을 -1(안되는 경우) , 0(아직 방문하지 않은 곳) , 1(되는 경우)로 구분하여 문제를 해결하였습니다. 출력때문에 시간이..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에는 dfs들어갈 때 visited배열을 true로 해주고 끝날 때 false로 해주지 않아 틀렸습니다. 그 다음으로는 DP를 적용시키지 않아서 시간초과가 나왔습니다. 일반적인 경로 DP로 짜게되면 무한문이 발생하여 스택오버플로우가 발생할 수 있습니다. 그래서 visited배열과 DP배열을 같이 사용하였습니다. package BOJ; import java.io.BufferedReader; im..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 전형적인 다익스트라 문제이다. 저는 다익스트라를 통해 최소 값을 알아냈고, route라는 경로 배열을 통해 이전 최소값의 경로들을 저장하였습니다. 또한, Stack은 Vector로 구현되어 있어 동기화 기능이 내재되어 있어 효율적이지 않은 것으로 알고 있습니다. 그래서 deque를 통해 stack을 사용하였습니다. package BOJ; import java.io...

https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 해당 문제는 DFS방법으로 풀었습니다. 뎁스가 깊어질수록 cnt를 늘려주고 더 이상 갈 곳이 없다면(리프노트) cnt의 값을 결과값에 더해주었습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import jav..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 저는 플루이드-워샬 알고리즘을 활용하여 2-칭구를 찾았습니다. 플루이드-워샬은 n^3방법으로 비효율적일 수 있지만 코드가 간결하고 입력값이 50이라 시간초과가 나지 않을 것이라 판단하여 사용하였습니다. 마지막으로 각 행에 대한 Y를 찾고 이 수가 가장 큰 값을 결과로 출력하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputSt..