본문 바로가기
728x90

전체 글

 (229)
[백준][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이면 결과를 출력한다...
[백준][코틀린][4574] 스도미노쿠 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 문제 풀이 1. sudomiku 배열을 선언하고 주어진 입력을 저장한다. 2. 완전 탐색을 수행한다. 이때 9 X 9 의 보드판이므로 완전 탐색의 depth 가 81이 되면 결과를 출력한다. 3. depth 81 인 경우가 여러 가지가 나올 수 있으므로 completed flag 를 설정하여 출력은 한 번 하면 다음번 depth(81) 조건을 만족하는 경우는 무시한다. 4. 도미노..
[백준][코틀린][12100] 2048 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 1. board 정보를 저장하는 2차원 배열을 선언한다. 2. 현재 board 판의 정보과 이동 횟수를 저장하는 Queue 선언하고 BFS 탐색을 한다. 3. 상/하/좌/우를 탐색한다. 이때 문제에서 주어진 숫자가 합쳐지는 경우를 처리하기 위해서 stack 에 저장한다. 4. 한 번 합쳐진 블록은 합쳐지지 않으므로 stack 을 처리할 때 combined f..

티스토리툴바