- Today
- Total
목록dfs (51)
개발하는 고라니
16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net [DFS] DFS를 이용해 A ~ Z로 이루어진 격자에서 사이클이 존재하는지 여부만 판단하면 된다. 사이클을 확인하는 알고리즘은 다음과 같이 작성했다. static boolean visit = new boolean[51][51]; static boolean cycle; /* 현재 방문하고 있는 정점이 이미 방문되었고, cnt가 4이상이면 cycle을 찾았다고 판단 */ static void DFS(int y, int x, int bY, int bX, in..
16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net [DFS] 백준의 다리 놓기(?) 시리즈 문제였나 그거랑 좀 비슷한 것 같다. 나의 문제 접근법은 다음과 같다. 지도를 입력 받으며 '0'인 곳은 Queue에 넣는다. DFS를 이용해 1로 이루어진 덩어리(모양)을 탐색하고, 그 덩어리에 ID(인덱스)를 부여하며, 그 id가 갖는 크기를 Map에 저장한다. Queue에서 하나씩 빼며 상하좌우 인접한 덩어리의 크기를 모두 더한다. (단, 덩어리가 중복되지 않게 하기 위해 Set을 이용했다.) 3번을 반복하..
16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net [DFS + BFS] DFS로 순환을 찾아내고, 찾아낸 사이클에 포함된 정점들에서 BFS를 수행해 사이클이 아닌 정점들까지의 거리를 구한다. 처음에 이 DFS로 사이클을 찾아내는 방법을 잘 모르겠어서, 방문한 정점을 문자열에 담아 사이클을 찾으면 그것을 따로 저장하는 식으로 해서 문제를 풀었었는데, 어디가 틀린지 도저히 못찾겠어서 패스하고 다시 풀었다. 하지만 이번에도 어렵게 느껴져서 결국 다른 분의 코드를 참고해서 풀었다. 참고: ky..
16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [Dijkstra] BFS로 풀어보았으나 풀다보니 다익스트라 알고리즘이 더 풀기 쉬울 것 같아서 급히 방향을 바꾸어서 풀었다. map[ ]이라는 배열을 만들어서 i번 째 원소의 값은 i로 초기화한다. 그리고 n, m만큼 뱀과 사다리의 정보를 받아 해당 map[ i ]의 값을 바꾸고 다익스트라 알고리즘을 수행하면 된다. # Code import java.io.BufferedReader; import java.io.IOE..
16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net [BFS] 최소 이동 횟수를 찾는 문제는 DFS보다 BFS가 확실하다. BFS는 모든 방향으로 한 칸씩 나아가지만, DFS는 한 방향으로 끝을 볼 때 까지 나아가기 때문이다. BFS를 이용해 N x N 맵이 있다고 가정하고 탐색할 수 있는 맵을 모두 탐색할 때 까지 도착점에 도달하지 못하면 -1을 반환한다. # Code import java.io.BufferedReader; import..
17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net [DFS] 등수를 알고싶은 x번째 정점에서 DFS를 2번 수행 해야하므로 인접리스트를 2개 만든다. 입력으로 A B가 주어졌을 때, list[B][0].add(A), list[A][1].add(B) 처럼 2개의 인접리스트를 만들면 된다. DFS의 내부는 간단하다. 기본적으로 int rank = 1을 갖고 인접리스트를 돌며 방문하지 않은 정점을 돌며 계속 그 값을 더해나간다. static int DFS..
16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net [DFS] 주어진 방향 지도가 있을 때, (1) 사이클이 있을 때, (2) 방향을 따라가다 벽에 막히는 곳이 있을 때 'SAFE ZONE'을 설치하면 된다. 주어진 예제 입력으로 지도를 그려보자. 편의상 U = 0, D = 1, L = 2, R = 3으로 표기하겠다. 1 2 2 2 1 3 2 0 3 3 3 0 위와 같이 지도가 주어지고, 빨간색은 사이클이 존재하는 곳, 파란색도 사이클이 존재하는 곳이다. 저 두 개의 사이클 중 ..
16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net [DFS] 예시에 주어진 테스트 케이스 이외에 내가 만들어본 테스트 케이스이다. 이 예제가 DFS에서 조건처리해야 할 모든 것을 담고있다고 생각된다. 처음에 시간초과가 나게 풀었던 것은 모든 리프노드들에서 시작해 정점 1(Root)로 도착하며 그 때의 양이 몇마리 살아갔는지를 계산했었다. 하지만 그렇게 하면 이미 방문했었던 정점을 또 다시 방문하는 일이 발생한다. 그래서 시간초과를 받은 것 같다. 그래서 트리라는 것을 감안해 후위 순회(좌 - 우..