- Today
- Total
목록dfs (51)
개발하는 고라니
1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net [DFS or BFS] 2차원 배열이 map으로 주어지는 문제에서는 늘 BFS로 풀었어서 이번엔 DFS로 풀어보았다. B와 W로 이루어진 지도를 char로 그대로 저장하지 않고 boolean으로 저장하였다. W 이면 true로, B이면 false로. 물론 char[][]로 저장하여도 상관없다. 이제 2차원 배열 모든 정점을 방문할 차례인데, B로 이루어진 덩어리와 W로 이루어진 덩어리의 개수를 Math.pow해서 반환하도록 했다. DFS..
17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net [DFS + 동적 프로그래밍] 동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고... 이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할..
1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net [DFS] 문제의 주어진 입력을 토대로 N x N 크기의 단방향 인접 행렬을 만들었다. 그리고 마지막 줄에서 제거할 노드의 번호를 입력 받는데, 이 때 제거할 노드를 방문 했다고 처리한다. 이제 DFS를 수행할 차례인데, 만약 root 노드와 제거할 노드가 동일하다면 DFS를 수행해서는 안된다. 따라서 root노드와 제거할 노드가 다르다면 DFS를 수행한다. 이때 DFS는 다음과 같은 로직을 갖는다. static void DFS(int x){ visit[x..
1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [DFS + 백트래킹 + 비트마스킹] DFS를 이용해 백트래킹을 구현했고, 알파벳 'a' ~ 'z'까지 어떤 알파벳을 알고 있는지에 대한 정보를 비트마스킹으로 표현했다. 즉, 'a', 'b'를 알고있다면 0b00 0000 0000 0000 0000 0000 0011로 나타낼 수 있다. 그런데 남극의 단어는 "anta"로 시작해서 "tica"로 끝난다고 했으니, 'a', 'c', 'n', 't', 'i'는 반드시 알고있어야 한다. 그래서 check를 다음과..
6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 DFS 탐색 -> 방문 취소 가 이뤄져야 한다. # Code import java.io.BufferedReader; import java.io.IOException; i..
15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net [DFS] 몇 시간을 고민해보아도 풀지 못해 풀이를 찾아 보던 중, 너무 간단하게 푼 풀이가 있어 많은 것을 깨달았다. 나는 아직 DFS 응용을 하기에는 벅차다는 것을.. 문제의 실마리를 찾을 때 조금 더 집중하고 깊이 들여다보는 습관을 길러야겠다. 다음 풀이는 Sleeping Rabbit님의 블로그를 참고하였다. 리프노드의 높이를 구하고, 각 리프노드들의 높이를 모두 더한 합이 짝수이면 실패, 홀수이면 성공 이라는 간단한 명제로 풀이를 진행하셨는데, 내가 너무 ..
2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [BFS] 전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이... 각 정점은 0~15를 갖을 수 있는데, 0 : 벽이 없음 1 : 서쪽으로 벽 2 : 북쪽으로 벽 4 : 동쪽으로 벽 8 : 남쪽으로 벽 이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳) #풀이 요약 1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2..
2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net [DFS] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static StringBuilder sb = new StringBuilder(); static boolean isPrime(int x){ if(x == 1) return false; for(int i=2..