개발하는 고라니

17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net [BFS + 비트마스크] N x M 격자 맵에서 'X'로 표시된 모든 물건을 챙기고 탈출구 'E'로 최소한의 움직임으로 나가는 방법을 찾는 문제. 격자의 크기 제한이 최대 50x50이고 물건의 개수가 최대 5개라서 비트마스킹을 안써도 메모리적인 부분에서 큰 손실은 없을 것 같으나, 물건이 모두 'X'로 동일하여 현재 내가 특정 정점에 방문했을 때, 어떤 물건을 갖고 있는 지를 체크하는 것이 비트마스킹만큼 좋은 것이 없기에 비트마스킹을 사용했다. 먼저 입력을..

12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net [BFS] 브루트포스로 푼다면 문제 자체의 난이도는 비교적 간단한 편이나, 브루트 포스로 푼다면 메모리 소모가 엄청나므로 최대한 효율적인 방법으로 중복 점을 제거하여야 한다. 여러 방법이 있을 수 있다. 나는 정렬을 사용했다. 브루트 포스를 사용한다면 방문을 체크하는 정점 배열을 [1501][1501][1501] 만큼의 배열을 사용해야하지만, 정렬을 사용하면 [501][1001][1501] 정도의 크기로 줄일 수 있다. 돌의 개수는 최대 1500개를 넘지 않으..

16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net [BFS] 나는 입력으로 주어지는 지도를 저장할 때, int[ ][ ]가 아닌 boolean[ ][ ]에 저장했다. 이유는 추후 연산이 오래 걸릴 것을 감안해서이다. 아무래도 숫자 비교 연산보다 boolean 연산이 훨씬 빠르다고 생각했다. 어쨋든 N x M 직사각형 안에 H x W 크기의 직사각형이 하나 더 들어있는데, 벽을 피해서 가장 왼쪽 위의 꼭지점을 목적지로 이동하는 문제라고 파악했다. 매번 직사각형을 옮기며 모든 꼭지점에 벽이 ..

14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net [BFS] 아마 기억 상 '벽 부수고 이동하기 1' 문제와 90% 유사한 문제 같다. [백준] 2206번 : 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하 dev-gorany.tistory.com BFS를 수행할 때 Queue안에 들어가는 원소는 4개이다. [..

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

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 위와 같이 지도가 주어지고, 빨간색은 사이클이 존재하는 곳, 파란색도 사이클이 존재하는 곳이다. 저 두 개의 사이클 중 ..

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