알고리즘(w.KOTLIN)/그래프(bfs, dfs, 다익스트라) (32) 썸네일형 리스트형 [백준][코틀린][1697] 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 1. N 을 시작 지점, K 를 목표 지점으로 하여 BFS 를 수행한다. 2. 이때 시작 시점과 목표 지점이 같으면 탐색을 종료 한다. 3. 큐에는 (시작 지점, 현재까지의 걸린 시간) 을 저장한다. 4. BFS 에서 (앞으로 걷는 경우, 뒤로 걷는 경우, 순간 이동 하는 경우) 에 대해서 탐색한다. 코드 import java.io.* import java.u.. [백준][코틀린][2146] 다리 만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 풀이 1. 주어진 입력의 각 섬을 구분하기 위해서 BFS 를 이용하여 각 섬에 번호를 부여 한다. 예시의 경우 1, 2, 3 번 섬까지 부여된다. 2. 1번에 섬의 번호가 업데이트 된 map 배열을 이용하여 BFS 를 통해서 다리 길이의 최소 값을 전체 탐색한다. 2-1. 섬인 영역을 기준으로 탐색한다. 2-2. BFS 탐색 시 영역을 벗어나거나 이미 방문했거나 기준이 되는 섬과 같은 섬 지역은 .. [백준][코틀린][16947] 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제 풀이 1. 문제의 조건에서 순환선이 되는 경우를 찾고 순환선에 포함되는 역을 구한다. 2. 역과 역간의 정보를 연결 리스트로 저장한다. 3. 역 1번부터 N 번까지 DFS 로 탐색하여 순환선이 되는 경우에 대해서 포함되는 역을 찾는 탐색을 한다. 3-1. 현재 역(current), 순환 지점 역(taget), 이전 역(prev) 를 매개변수로 하여 탐색한다. 3-2.. [백준][KOTLIN][16929] Two Dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 풀이 1. 싸이클에 대한 조건을 확인하여 DFS 를 이용한다. 2. DFS 탈출 조건은 싸이클을 만족할 때 탈출되도록 하고 아니면 전체 탐색 한다. 3. 싸이클이 되기 위해서 depth 가 4보다 크거나 같고 시작 (x, y) 와 새롭게 탐색되는 점이 같은 지 확인 한다. 코드 import java.io.* private var result = "No" fun main(args: A.. [백준][KOTLIN][7576] 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 1. 주어진 토마토 정보에서 토마토가 있는 칸을 기준으로 BFS 를 수행한다. 이때 토마토가 들어있는 칸 인접 칸들은 동시에 익기 때문에 해당 부분을 고려해서 토마토 정보에서 토마토가 있는 칸(1)을 저장하는 ripenList Queue 를 선언한다. 2. ripenList 에 있는 queue 를 탐색할때 마다 result 를 증가 시킨다. 3. tomato 정보가 범위.. [백준][KOTLIN][13023] ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 풀이 1. 주어진 친구 관계를 저장하는 인접 리스트 배열을 선언한다. (val friend = Array(N) { ArrayList() }) 2. 친구의 수 0 부터 N-1 까지 반복하여 DFS 로 탐색한다. 이때 처음 시작되는 친구는 방문했으므로 visit[i] 를 true 로 설정하고 DFS 탐색한다. 3. depth 가 4 일 경우 주어진 조건과 같은 친구 관계가 되었으므로 결과를 1로 출력하고 그외에는 0으로 출력한다. 코드 import java.io.* private var result .. [알고리즘][KOTLIN] 양궁대회 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 쏴야할 화살의 개수를 저장하는 max 를 선언한다. 2. 라이언이 쏜 화살 정보를 저장하는 result List 를 선언한다. 3. dfs 를 이용하여 어피치 화살 정보를 완전탐색하여 라이언이 이기는 경우는 탐색 한다. 3-1. 라이언의 남은 화살 개수(arrow)가 0이 되면 dfs 탈출 조건으로 result list 에 결과를 업데이트 한다. 3-2. index i 가 10일 .. [알고리즘][KOTLIN] 혼자 놀기의 달인 https://school.programmers.co.kr/learn/courses/30/lessons/131130 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 상자와 카드를 저장하는 box map 을 선언하고 입력으로 들어오는 cards 의 index + 1 을 map 의 key 로 넣고 cards 의 value 를 map 의 value 에 저장한다. 2. 열은 상자를 확인하는 visit 배열을 선언한다. 3. bfs 를 이용하여 상자를 더 이상 열 수 없을 때 까지 반복한다. 4. 이때 3번에서 나온 결과가 상자의 개수와 같으면 문제.. 이전 1 2 3 4 다음