- Today
- Total
목록그래프 탐색 (57)
개발하는 고라니
17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [BFS] 백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다. 예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저..
16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net [BFS] 문제의 난이도는 그렇게 높진 않으나 접근하기가 까다로웠다. 각 층은 4방향을 가질 수 있고, 1~5층에 어떤 것을 넣든지 사용자의 결정이다. 사실상 브루트포스로 풀었다. 먼저 입력을 받을 때 원 방향, 90도, 180도, -90도 회전시킨 판의 모양을 저장한다. for(int i=1; i
16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net [BFS] 사람이 먼저 BFS 탐색을 하고, 그 다음 벽이 움직이는 벽 BFS가 실행된다.이 문제에서, 벽은 8턴 이후에는 맵에 없으므로(8줄이기 때문에 8턴 후 모든 벽은 사라진다) 9턴 째 까지 왔다면 탐색할 필요 없이 탈출에 성공한 것이다. 그래서 visit배열을 3차원 배열로 선언해 몇 번째 턴일 때 방문한 것인지 체크하였다. 플레이어는 상하좌우, 대각선, 제자리 이렇게 9곳을 탐색할 수 있다. 그리고 가장중요한 것은 다음과 같은 상황일 때의 처..
13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [BFS] 정답률 25%를 과시라도 하듯 결코 쉽지않은 문제이다. 문제에 주어진 조건 중 몇 가지가 특히 어떻게 접근해야할지 난해했다. 그 중에 '빨간 구슬(R)과 파란 구슬(B)은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.' 가 특히나 골치아팠다. static class Point{ int y, x; public Point(int yy, int xx){ y=y..
2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [BFS] 전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이... 각 정점은 0~15를 갖을 수 있는데, 0 : 벽이 없음 1 : 서쪽으로 벽 2 : 북쪽으로 벽 4 : 동쪽으로 벽 8 : 남쪽으로 벽 이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳) #풀이 요약 1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2..
6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net [BFS] 바로 본론부터 얘기하자면, 일반적인 BFS와 다른 점이 존재한다. 바로 각 정점은 방향을 갖는다는 것이다. 여기서 방향이란 상하좌우를 의미한다. 방향이 존재하므로 배열도 3차원이 되어야한다. 예를 들어 방문했는지에 대한 체크하는 배열 visit[ ][ ][4], 각 정점에서 해당 방향으로 도착했을 때의 거울이 몇개 필요했는지에 대한 배열 mir[ ][ ][4]. 이뿐만이 아니다. 레이저와 거울의 특성을 고려해보면, 레이저를 거울에 비추었을 때..
13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net [Floyd-Warshall or 다익스트라] 나는 플로이드-와샬로 풀었으나, 다익스트라로 푸는 것이 어쩌면 더 적은 시간이 들지도 모르겠다. 다익스트라를 사용한다면 k번의 다익스트라를 수행하게 되니까 말이다. 일반적인 플로이드 와샬 문제처럼 거리의 대한 배열 dist를 i == j일때는 0으로, 아닐때는 INF로 초기화 해놓고, 입력에 따라 dist에 값을 대입한다. for(int i=1; i
10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net [크루스칼 알고리즘] 보통 MST하면 모든 정점이 하나의 덩어리로 연결되는 것을 생각할 수 있는데, 이 문제의 경우 발전소의 개수(k)개의 덩어리로 나뉘어 모든 정점이 연결되었을 때의 합을 출력하는 문제이다. 나는 유니온-파인드 부분을 수정했다. 보통 유니온-파인드는 두 정점 a, b를 받아 더 작은 번호를 부모 노드로 삼는 것이 일반적인데, Set에 발전소의 번호를 넣어두고 1) 두 정점 모두 발전소에 연결되어있지 않다..