https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 우선순위 큐를 이용한 BFS 벽을 최소한으로 부숴야 하기 때문에 BFS를 선택했다. 단, 그냥 큐를 사용해서 풀 경우에는 움직인 거리 기준으로 큐에 들어가기 때문에, 우선순위 큐를 사용하여 벽을 부순 횟수를 기준으로 정렬되도록 했다. 처음에는 방문 체크 배열 v를 int 배열로 만들어 어떤 위치에 도달했을 때, 그 때까지 부순 벽의 개수를 저장하려 했는데, 어차피 벽을 부순 ..
BFS
https://www.acmicpc.net/problem/30206 30206번: 차량 배치 첫 번째 줄에 지점의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 200\,000;$ $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200\,000))$ 이후 $M$개의 줄에 걸쳐 각 도로가 잇는 서로 다른 www.acmicpc.net 경우의 수 구하기 조건과 설명만 읽고 복잡해보일 수 있지만, 사실 뜯어보면 간단하기 그지없는 문제이다. 모든 연결은 가중치 1을 갖기 때문에 BFS로 1번 도로와의 거리를 구할 수 있다. 1번 도로까지의 거리를 깊이 라고 하자. 어떤 도로에서도 충돌이 일어나면 안되기 때문에, 깊이가 같은 도로가 두 개 이상이..
https://www.acmicpc.net/problem/17472 [17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net](https://www.acmicpc.net/problem/17472) 섬 구분하기 일단은 각 섬을 구분하기 위해 init_land 함수를 구현했다. 섬을 구분하도록 하는 변수 group을 2로 두고, BFS로 근처 땅을 모두 group으로 초기화하도록 했다. 섬 하나에 속한 땅을 모두 group으로 바꾼 후에는 1 증가하고 다음 땅을 찾는다. 즉, init_land 이후 ..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net BFS "최소 거리"를 구해야 하기 때문에 BFS를 사용해야 한다. 처음에는 열쇠 조건을 배열로 만들려고 DFS로 구현했었는데 시간 초과가 나왔다. BFS로 바꾸니까 통과할 수 있었다. 방문 체크 처음에 DFS를 사용했던 게 방문 체크에 조건이 복잡했기 때문이다. 만일 단순히 v[N][M]으로 체크를 해준다면, 막다른 길에 열쇠가 있을 때 열쇠를 갖고도 다시 못 돌아..
https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net BFS (2056ms) 각 간선을 List로 저장하고 Query가 주어질 때마다 간선 리스트를 바탕으로 BFS로 갈 수 있는 노드를 찾도록 했다. 단순한 방법으로 통과하기는 했지만 시간이 2056ms나 나왔다. N개의 노드에 N - 1개의 간선이 있고, 모든 노드가 이어져 있다는 조건으로, 사이클이 없는 트리 구조라는 것을 활용해보고 싶었지만 떠..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net BFS 어떤 편의점을 방문해야할지 모르기 때문에 BFS를 사용했다. 가장 먼저 떠올린 것은 가까이 있는 순서대로 방문하는 것이었으나, 가장 가까이 있는 편의점이 오히려 공연장과 멀어지거나, 혹은 다른 편의점들과 거리가 멀어 다음 편의점에 도달하지 못하는 경우가 있을 수 있다. 따라서 현재 위치에서 방문할 수 있는 경우를 Queue에 담아두고, 그곳에서 다시 방문할 수 있는 곳을 찾는 게 합리..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 물과 고슴도치의 순서 문제 조건 중에 이해하기 어려웠던 부분이 있었다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이 부분인데, 물이 차오름과 동시에 고슴도치가 이동하니, 그 다음턴까지 파악을 해야 하나 하는 생각이 들었었다. 하지만 결국 정답은 물을 먼저 채우고, 그 다음 고슴도..
https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net Queue 배열 "번호가 낮은 바이러스부터 증식한다" 라는 조건이 있기 때문에 Queue를 여러 개 사용하기로 했다. 큐 배열을 만들어서 각 번호를 인덱스로 위치를 저장하는 것이다. 그리고 매초마다 반복해야 하기 때문에 time이라는 변수를 두고, 큐에도 시간을 넣어 저장하도록 했다. 전체 코드 // 시간: 272ms // 메모리 : 19728KB public cla..
