개발하는 고라니

문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1..

코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr [DFS + 백트래킹] 시작 단어에서 목표 단어까지 최소 몇번의 변환을 거쳐 도달할 수 있는지에 대한 문제이다. 주어진 단어 배열의 각 원소를 하나의 정점(V)로 보고, 방문했는지에 대한 체크 값을 잘 사용하면 어렵지 않게 풀 수 있다. 코드가 그리 복잡하지 않고 주석이 있으므로 함께 보면 더 이해가 빠를 것 같다. Code package org.gorany.programmers.단어변환; class Solution {..

코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [DFS + 백트래킹] 1) 도시에 각각 고유 번호를 부여해서 , 맵을 각각 만든다. 2) 도시 번호와 도시명이 있으니 티켓을 반복해 돌며 인접리스트를 만든다. 3) 탐색을 한다. /* * ticketSize = 주어진 티켓이 총 몇장인지? * size = 현재 티켓을 몇 장째 처리하고 있는지 * cur = 현재 방문하고 있는 도시의 번호 * */ static boolean DFS(int ticketSize, int size, ..

4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net [DFS] 다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다. 사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다. static boolean DFS..

2017 카카오코드 본선 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr [DFS + 백트래킹] 문제의 이해도는 어렵지 않은 편이었으나, 출력 형식에 주어진 문구가 마음에 안들었다. 해는 여러가지 일테니, 알파벳 순으로 가장 먼저인 답을 출력하라니... 열심히 풀었건만 저 문장 때문에 코드를 싹 갈아엎었다. 다른 사람들은 타일을 깰 수 있는 조건으로 현재 타일에서 수평/수직/왼쪽 위, 아래/오른쪽 위, 아래 타일이 있을 때 이렇게 나누어서 한 것 같다. 나는 그냥 탐색하도록 했다. 예를 들어 현재 ..

3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net [DFS] N x N 격자의 밖에서 레이저빔을 쐈을 때 우향우 거울을 통해 반사되어 최종적으로 레이저빔이 도착한 위치를 찾는 문제. 레이저 빔은 이미 지나온 곳도 다시 지날 수 있다. 그렇다고 해서 방문을 했는지 여부를 체크하지 않으면 안된다. 문제에서 주어진 것을 보면 알 수 있듯, 레이저빔이 격자 밖을 빠져나가지 못하면 0 0을 출력하라고 한 것을 보아 방문을 체크하지 않는다면 무한루프에 빠져 Stackoverflow 에러가 발생할 것이다. 그러면 어떻게 방..

2017 카카오 코드 예선 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr [DFS or BFS] 다른 방법도 있겠지만 DFS나 BFS를 사용해 '0'이 아닌 곳을 찾고, 같은 숫자로 연결(상,하,좌,우 인접)된 area 개수를 카운트하고, 각 area의 크기(Size)를 구해 최댓값을 도출하면 된다. 각 영역의 사이즈를 구하는 방법은 특정 정점을 방문할 때 마다 1을 기본값을 가지고 연결된 지역을 돌며 그 개수만큼 더한 값을 반환한다. # Code class Solution { static int[] Y = ..

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개의 같은 색인 인접(상하좌우)한 세..