본문 바로가기
728x90

알고리즘(w.KOTLIN)/그래프(bfs, dfs, 다익스트라)

 (32)
[백준][코틀린][14442] 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 1. BOJ 2206 과 매우 유사한 문제 이다. 2. 다른 점은 2206 과 달리 벽을 부술 수 있는 개수가 입력으로 주어진다. 3. 따라서 BOJ2206 풀이 visit 배열을 3중 배열로 선언하는 부분을 조건에 맞게 변경한다. 0th Index : 벽을 부순 개수, 1st Index : 현재 위치 X 좌표, 2nd Index : 현재 위치 Y좌표..
[백준][KOTLIN][2206] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 1. 이중 for 문을 이용하여 벽을 하나씩 부순 후 bfs 를 탐색할 경우 시간 초과가 발생한다. 2. bfs 탐색시 visit 방문 배열을 3중 배열로 선언한다. 1st Index : N, 2nd Index : M, 3rd Index : 벽돌 부순 유무 3. 처음 시작 지점(1, 1) 은 벽돌 부순 유무를 모두 true 로 설정한다. 4. queue 에는 현..
[백준][코틀린][12886] 돌 그룹 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 문제 풀이 1. 입력으로 주어지는 세 수를 queue 에 저장하고 BFS 를 수행한다. 2. 세 개의 수 중 서로 같지 않은 두 개의 수를 선택하기 때문에 아래의 3가지 경우에 대해서 반복 탐색 한다. - (A, B), (A, C), (B, C) 3. 나머지 하나의 수는 세 수의 합에서 2번에서 선택된 두 수의 합을 뺀 값이다. 4. 따라서 이미 수행했는 지 여부를 확인하는 visit 배열은..
[백준][코틀린][14502] 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 1. 2차원 배열 map 에 입력으로 주어지는 연구소 정보를 저장한다. 2. map 정보에서 초기 바이러스 정보를 virus 2차원 Boolean 배열에 저장한다. 3. 벽을 3개 세우는 것을 구하기 위해서 DFS 를 수행한다. 3-1. depth 가 3이 될때 바이러스 감염 범위를 탐색하여 안전 지역의 개수를 확인한다. 3-2. map 의 값이 0인 곳을 확인하여 1로 업데이트 한다. 4. 바이러..
[백준][코틀린][9019] DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 풀이 1. A, B 숫자 입력을 받는다. 2. A == B 가 될때까지 BFS 를 이용하여 탐색한다. 3. (현재 숫자, 수행된 명령어)를 저장하는 Queue를 선언한다. 4. visit 배열을 선언하고 크기를 10,001 로 잡는다. 숫자가 이미 사용되었는 지 유무를 확인하는 배열로 사용한다. 5. D 명령어는 문제 따라 nextNum * 2 % 10,000 의 값으로 처리한다..
[백준][코틀린][16948] 데스 나이트 https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 문제 풀이 1. N X N 크기의 2차원 BooleanArray visit 를 선언하여 이미 탐색했는 지 유무를 저장한다. 2. Position data class 를 선언하고 r, c 좌표를 파라미터로 받는다. 3. DeathNight data class 를 선언하고 Position, Count(이동 횟수) 를 파..
[백준][코틀린][16928] 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 풀이 1. 사다리의 정보와 뱀의 정보를 Int배열에 저장한다. 사다리와 뱀의 정보가 서로 다른 위치의 값이므로 하나의 Int배열에 저장해도 무방하다. 2. 사다리의 x, 뱀의 u 를 index 로 하고 y, v를 value 하여 배열에 저장한다. 3. 1번째부터 시작하여 BFS 를 이용하여 탐색한다. 4. 현재 위치가 100이면 결과를 출력한다...
[백준][코틀린][13460] 구슬 탈출2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 풀이 1. 주어진 입력은 board 2차원 배열에 저장한다. 이때 R/B 구슬의 위치를 Marble Data Class 에 저장하고 board 의 값은 빈칸 영역인 "." 으로 바꾼다. 2. 붉은 색, 푸른 색 구슬과 현재 움직인 횟수를 저장하는 Marble Data Class 를 선언한다. 3. 구슬의 위치를 시작으로 하는 BFS 탐색을 수..

티스토리툴바