개발하는 고라니

16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net [DFS + BFS] DFS로 순환을 찾아내고, 찾아낸 사이클에 포함된 정점들에서 BFS를 수행해 사이클이 아닌 정점들까지의 거리를 구한다. 처음에 이 DFS로 사이클을 찾아내는 방법을 잘 모르겠어서, 방문한 정점을 문자열에 담아 사이클을 찾으면 그것을 따로 저장하는 식으로 해서 문제를 풀었었는데, 어디가 틀린지 도저히 못찾겠어서 패스하고 다시 풀었다. 하지만 이번에도 어렵게 느껴져서 결국 다른 분의 코드를 참고해서 풀었다. 참고: ky..

16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [BFS] 백준의 '벽 부수고 이동하기' 시리즈의 3번째 문제이다. 벽을 부술 수 있는 개수가 K개로 한정되어있고, 벽을 부수는 조건은 '낮'에만 부술 수 있으므로 이 점을 잘 고려해야한다. 방문한 것을 체크하는 visit는 4차원 배열로 선언했다. 해당 좌표에 밤에 갔을 때, 낮에 갔을 때, 그리고 벽을 n개 부쉈을 때. visit[1001][1001][11][2] Queue에 들어가는 원소는 5개이다. 좌표값 y, x 몇 번..

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

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

17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [BFS] 백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다. 예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저..

12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [문자열 + BFS] 이 문제는 정공법으로 풀면 안된다. s -> t를 가는게 아닌, t -> s를 가는 것을 생각해야 한다. 전자로 풀면 메모리 초과가 날 수 있다. 따라서 t -> s로 가는 방법으로 풀어보자. 1. 문자열의 끝이 'A'이면 맨 끝 문자 삭제 2. 문자열의 끝이 'B'이면 맨 끝 문자 삭제 후 뒤집기 나는 Set을 이용해 방문을 표시했엇으나, 굳이 필요하지 않음을 느꼈다. 따라서 반복문의 종료 조건은 문자열..