개발하는 고라니

14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net [크루스칼] 최소 스패닝 트리를 만드는 문제인데 약간 문제에 낚였다고 해야하나.. "만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다." 라는 문장 때문에 항상 부모가 1번 도시와 연결되어있어야 하는 줄 알고 풀었더니 시간이 2s가 넘게 걸렸다. 아무리 생각해도 이건 아닌 것 같아 일반적인 크루스칼 알고리즘 처럼 풀었더니 정답으로 인정되었다. 코드로 보는 것이 더 이해가 쉬울 듯 하다. int sum = 0;..

2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net [배열] Javascript로 문제풀이를 익히기 위해 풀어본 문제. # Code const readline = require('readline'); var rl = readline.createInterface({ input: process.stdin, output: process.stdout }); var arr = []; rl.on('line', (input)=>{ arr.push(input); }).on('close', ()=..

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

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