개발하는 고라니

16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net [BFS] 문제에서 주어진 B 버튼을 눌렀을 때의 기능을 잘 구현할 수 있다면 어렵지않게 해결할 수 있을 문제. B는 n을 2배로 증가하고 0이 아닌 가장 높은 자릿수의 값을 1 감소시키는 기능이므로 2번의 반복문을 사용하여 해결하였다. static int B(int x){ int result = 0, idx = 10; int[] arr = new int[5]; for(int i=0, k=10000; i

16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net [다익스트라] 오랜만에 다익스트라 알고리즘 문제를 풀어볼까 해서 여유롭게 푸는가 했으나 너무 안일하게 생각했던 문제. 여우는 문제없이 최단거리를 구할 수 있겠는데.... 늑대는 속도가 x2배 일 수도, 0.5배 일 수도 있으므로 조금 고민해보지 않으면 쉽지 않은 문제인 것 같다. 도대체 어떻게 접근해야할지 떠오르질 않아 질문 게시판을 보다가 아 이거구나 하는 질문을 찾았다. 링크는 하단에 공유하도록 한다. ..

17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net [BFS] 우리는 생각해야한다. '그람'을 얻었을 때와 얻지 않았을 때의 visit를. 즉 visit는 3차원 배열로 선언했다. 이동한 횟수 move 또한 3차원 배열로 만들 수 있으나, 그냥 Queue의 원소로 넘겨주었다. 따라서 Queue의 원소에 들어가는 값은 총 4가지이다. static class Point{ int y, x, find, move; public Point(int yy, int xx, int find, int move){ y=..

13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net [DFS or BFS] 이런 2차원 배열이 주어지는 탐색문제에서 주로 BFS만 사용했어서 이번엔 DFS로 풀어보았다. 문제의 답을 도출하는 방법은 매우 단순하다. 첫째 줄에서 출발해서 검은 칸이 아닌 상하좌우 흰색 칸을 따라 마지막 줄까지 도달할 수 있는가? static boolean DFS(int y, int x){ if(y == r) return true; visit[y][x] = true; boolean result = f..

2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net [DFS] 입력 N은 홀수로만 주어지기 때문에 중간을 (n + 1) / 2로 표현한듯 하다. int[100][2] 배열을 준비하여 int[i][0]에는 i 구슬보다 가벼운 구슬, int[i][1]에는 i 구슬보다 무거운 구슬의 개수를 저장하도록 한다. n회 반복문을 돌며 현재 구슬의 무거운 구슬의 개수 또는 가벼운 구슬의 개수가 (n + 1) / 2개 이상일 때 그 구슬은 가운데의 구슬에 들어갈 수 없다. # Code import java.io..

1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net [플로이드 - 와샬, Floyd - Warshall] A, B, C, D, E가 있다고 하자. A와 B가 친구이고, B와 C가 친구일 때 A와 C는 친구이다. 그럼 C와 D가 친구일 때 A와 D는 친구일까? 아니다. 2-친구이므로 나의 친구의 친구까지만 친구로 인정된다. 따라서 D는 A의 3-친구이다. 이 문제에서는 2-친구만을 답으로 원하므로 플로이드 와샬을 수행하여 각 친구들이 n-친구인지 구하고 2 이하인 친구들의 개수를 구하도록 한다. (0일 때는 친구가 아..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net [BFS] 4가지의 함수를 구현하기만 하면 간단한 BFS이다. 이 문제의 핵심은 L()과 R()에서 얼마나 시간을 단축하느냐에 달린 것 같다. L, R 함수는 언뜻보면 간단하지만, 항상 4자리임을 가정하고 하는 것이라, 4자리 이하일 때 "0"을 채워 4자리를 만들어줘야한다. 이 과정이 노련한 사람에게는 짧고 간편한 코드로 작성할 수 있겠으나... 나같은 초심자에게는 잡기술을 동원해서 겨우 AC를 받아내었다. static int L(int x){ S..

1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net [BFS] 4자리 이면서 소수인 숫자를 한 자리씩 바꾸는데, 바꿔서 완성된 4자리 수도 소수이어야 한다. 그래서 목표 소수까지 가야하는데, 한 자리씩 어떻게 바꿀 것 인가에 대한 방법은 다양할 것이다. 나는 문자열로 변환하여 풀었다. 예를 들어 1033이라는 수가 있으면, 이를 문자열로 변환하고 1000의 자리, 100의 자리, 10의 자리, 1의 자리에 각각 0~9를 대입하며 (1) 방문했었는지 ? (2) 4자리 숫자인지 ? (3) 소수인지 ? 를 따져서 해당 조건을 ..