박카스러버

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 저는 중복제거를 위해 DP를 이용해 접근하였습니다. 또한 입력의 세번째 인자 값을 확인하여 배열에 순차적으로 넣지 않고 수학적으로 접근하여 행과 열을 구하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer..

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 저는 해당 문제를 위상정렬을 이용하였습니다. count배열을 통해 해당 노드가 사이클에 있는지 확인하였습니다. 사이클을 먼저 확인하고 사이클에서 각각의 노드에 dfs를 사용해 사이클과의 거리를 확인하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.u..

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