개발하는 고라니

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

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net [DFS] DFS를 이용해 A ~ Z로 이루어진 격자에서 사이클이 존재하는지 여부만 판단하면 된다. 사이클을 확인하는 알고리즘은 다음과 같이 작성했다. static boolean visit = new boolean[51][51]; static boolean cycle; /* 현재 방문하고 있는 정점이 이미 방문되었고, cnt가 4이상이면 cycle을 찾았다고 판단 */ static void DFS(int y, int x, int bY, int bX, in..

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

18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net [비트마스킹] 입력으로 N개의 단어가 문자열 형태로 주어지는데, 이를 문자열로 저장하는 것 보다, 어떤 알파벳이 있는지를 알고있으면 단어 전체를 보지 않더라도 이 단어를 알 수 있다. 따라서 String[ ]이 아닌, int[ ]에 저장하는 것이 바람직 할 것이다. 비트마스킹에 대해 잘 모른다면 간단하게 정리해둔 포스팅을 참고하자. [알고리즘] 비트 마스킹(Bit Masking) 비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다..