개발하는 고라니

16441번: 아기돼지와 늑대 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열 www.acmicpc.net [BFS] 빙판('+')만 주의하면 될 문제인줄 알고 섯불리 제출했다가 오답처리를 당했다. 그 이유는 조금 뒤에서 설명하고 우선 문제의 접근법은, 문제에서 주어진 입력을 받으며 늑대의 위치를 기억한다. 그리고 BFS 함수의 인자로 늑대들의 위치를 준다 늑대들의 위치에서 각자 BFS를 수행하는데, 빙판('+')을 만나면 산('#')이나 초원('.')을 만날 때 까지 쭉 미끄러진다. 이 부분을 구현하는 메서드는 다음과 같다. /* di..

16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net [DFS] 뿌요뿌요(?)와 비슷한 방식의 게임이라고 하며, 0은 빈 칸이고, 1~9로 이루어진 각각 다른 색의 세포가 10 x N 격자에 있는데 최소 K개의 같은 색인 인접(상하좌우)한 세..

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개를 넘지 않으..

1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 n || p[1].x-1 n) return false; for(int a=0; a n || map[log.y][log.x] == '1') return false; return true; } static boolean left(Point[] p){ for(Point log:p) if(log.x n || map[log.y][log.x] == '1') return false;..

16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net [DFS] 백준의 다리 놓기(?) 시리즈 문제였나 그거랑 좀 비슷한 것 같다. 나의 문제 접근법은 다음과 같다. 지도를 입력 받으며 '0'인 곳은 Queue에 넣는다. DFS를 이용해 1로 이루어진 덩어리(모양)을 탐색하고, 그 덩어리에 ID(인덱스)를 부여하며, 그 id가 갖는 크기를 Map에 저장한다. Queue에서 하나씩 빼며 상하좌우 인접한 덩어리의 크기를 모두 더한다. (단, 덩어리가 중복되지 않게 하기 위해 Set을 이용했다.) 3번을 반복하..

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개이다. [..