개발하는 고라니

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net [2개의 BFS] [백준] 5427번 : 불 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나 dev-gorany.tistory.com 위 문제와 매우 유사한 문제. 이번에는 map[r+2][c+2]의 배열을 만들어, 주어진 맵 테두리를 건물 밖으로 생각하고 풀었다. 이렇게 하면 좌표의 범위에 신경써야하는..

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net [우선순위 큐 + BFS] 우선순위 큐를 사용한 이유에 대해서는 이따 반례와 함께 언급하고, 큐에 들어가야 하는 원소는 4가지 이다. 위치의 좌표(y, x), direction, 명령을 실행한 횟수(cnt)이다. 방향은 4가지 (동:1, 서:2, 남:3, 북:4)이고, 각 칸으로 최대 3칸 까지 갈 수 있으므로, int[][] X = {{1, 2, 3}, {-1, -2, -3}, {0, 0, 0}, {0, 0, 0}} int[][] Y = {{0, 0, 0}, {0, 0,..

5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net [BFS] 이 문제를 depth가 2 이하인 곳만 탐색하는 DFS로 풀어보려 했으나 6 5 1 2 1 3 3 4 2 3 4 5 의 예제 입력에서, 3 -> 4를 도달하지 못한다. 1->2 그리고 2->3을 방문하기 때문에 1 -> 3, 3 -> 4를 가지 못하는 것이다. 이미 3 정점을 방문했기 때문이다. 그래서 한 층씩 탐색하는 BFS가 가장 적합한 방법이라고 생각된다. # Code public class Main { static class Element{ i..

5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net [BFS] 2개의 BFS를 이용해야한다. 불을 퍼트리는 fireBFS와 상근이를 한 칸씩 이동시키는 BFS(). fireBFS는 visit에 영향을 주지도, 받지도 않는 단순히 map[][]을 변형시키는 용도이다. 반면 BFS()는 visit에 밀접한 연관이 있으며 더 이상 이동할 수 없다는 사실과 상근이가 탈출했다는 사실을 반환해야한다. 더 이상 이동할 수 없다는 것은 임시 큐의 size가 0일 때이다.(상근이가 이동할 수 있는 곳이 X) 반면 상근이가 탈출했다는 것은 현..

13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [BFS] 백준의 숨바꼭질 시리즈 중 4번 째 문제. 이번에는 1초 뒤 -1, +1, *2 칸으로 이동할 수 있고, end에 도착했을 때 최소 시간과 그 때의 거쳐온 과정을 나열한다. 과정을 출력하는 것은, from[]이라는 배열을 준비하고, cur정점에서 next 정점으로 n만큼의 시간을 거쳐서 갈 때, from[next] = cur arr[next] = n visit[next] =true 한다. 이렇게 저장된 from[]에서 ..

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [BFS or Dijkstra] 백준 문제 시리즈 중 '벽 뚫고 이동하기'와 비슷한 유형의 문제이다. 최대 k번의 나이트(Knight) 이동을 이용해 (1, 1)에서 (r, c)로 최소한의 이동으로 가는 이동 횟수를 구하는데, 다익스트라나 BFS 둘 다 가능하지만, 다익스트라를 이용한 장점이 없으므로 BFS를 이용한 것이 400ms정도 더 빨랐다. (사실 동일한 코드이고, Queue를 쓰면 BFS, 우선순위 큐를 쓰면 다익스트라로 변신한다.) 현..

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net [BFS] main에서 하는 일은 단 4가지다. 1) visit 초기화 2) 맵 BFS로 스캔 하며 터트릴 것이 있다면 터트리고, flag = true로 설정(flag == false면 종료 시퀀스) 3) score++ 4) 블록들을 아래로 내려주는 down() 다시 1~4 반복. 2) 에서 Queue를 이용해 BFS를 구현하였고, 큐에 들어가는 좌표를 List에 담아 만약 4개 이상 담겼다면 터트리고 마지막에 List를 초기화시켰다. #..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [Union-Find] 입력은 인접 행렬 형태로 주어지지만, 크루스칼 알고리즘을 사용할 때 처럼 모든 간선의 정보를 하나의 리스트에 담았고, 이 리스트를 가지고 유니온 파인드를 하여 서로 연결된 그래프라면 연결시켰다. 그리고 입력으로 주어진 m개의 여행 도시 배열의 각 원소의 부모가 첫 번째 원소의 부모와 다르다면 이 여행 순서는 이루어질 수 없으므로 "NO"를 출력한다. # Code public class Main { static class Edge{ int ..