개발하는 고라니

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

11021번: A+B - 7 각 테스트 케이스마다 "Case #x: "를 출력한 다음, A+B를 출력한다. 테스트 케이스 번호는 1부터 시작한다. www.acmicpc.net 자바스크립트와 노드를 공부하며 백준도 자바스크립트로 풀어보고 싶은 마음에 첫 도전하는 자바스크립트로의 programming sovling. 첫 문제인 만큼 난이도도 아주 쉬운 것으로 정했다. 자바스크립트와 readline에 어서 익숙해져서 어려운 문제도 자바스크립트로 풀어보고 싶은 마음이 굴뚝같다. # Code var readline = require('readline'); var rl = readline.createInterface({ input: process.stdin, output: process.stdout }); func..

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) 비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다..

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