알고리즘(w.KOTLIN)/그래프(bfs, dfs, 다익스트라) (32) 썸네일형 리스트형 [백준][코틀린][14395] 4연산 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 풀이 1. 문제를 4가지 연산에 대해서 BFS 를 수행한다. 이때 연산자 순서(*, +, -, /) 에 맞게 탐색을 한다. 2. 이미 연산된 결과를 확인하기 위해서 Boolean 배열을 사용할 경우 10억개의 크기를 가지므로 에러가 발생하기 때문에 중복 조건을 확인할 수 있는 Set 자료구조를 사용한다. 3. 나눗셈 연산 시 탐색할 숫자가 0일 경우에는 다음 탐색을 수행한다. 코드 i.. [백준][코틀린][10026] 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 1. 주어진 입력을 picture 2차원 Char 배열에 저장한다. 2. BFS를 한 번 수행하여 정상인의 그림 숫자를 구한다. 3. 2번 BFS를 수행 후 Visit 배열을 초기화 하고 picture 배열의 R/G 값을 임의의 X 값으로 업데이트 한다. 4. BFS 를 추가로 수행하여 적록색양의 그림 숫자를 구한다. 코드 import java.io.* import java.ut.. [백준][코틀린][1963] 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 풀이 1. 주어진 입력을 BFS 를 통해서 완전 탐색 한다. 2. 주어진 숫자는 4자리이므로 천의 자리부터 일의 자리까지 탐색 한다. 3. 0 ~ 9 까지의 숫자를 바꿀 수 있으므로 각 경우에 대해서 탐색한다. 4. 이때 천의 자리가 0으로 올 수 없으므로 조건을 추가 한다. 5. 이전에 탐색한 숫자를 확인하기 위한 방문 배열 visit 를 선언한다. 6. 탐색하는 숫자가 현재 숫자와 같은 지 확인 .. [백준][코틀린][6087] 레이저 통신 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 1. 현재 위치(x, y), 현재 거울 개수, 레이저 방향을 저장하는 Laser Data Class 를 만든다. 2. 주어진 입력에서 C 지점을 laserArea 에 저장한다. 3. laserArea[0] 의 값을 시작으로 BFS 를 수행한다. 4. Queue 에는 1번에서 만든 Laser Class 를 넣고 초기 값으로는 3번에서 찾은 값을 넣는다. 이때 거울 개수를 -1 로.. [백준][16236] 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 1. 입력은 2차원 배열의 map 에 저장한다. 2. 상어의 위치를 찾고 상어가 이동하기 때문에 상어 위치의 값을 0으로 변경한다. 3. 처음 상어의 위치에서 잡아 먹을 수 있는 물고기를 모두 탐색한다.(상어 정보를 저장하는 queue 를 선언한다.) 4. 3번과정에 잡아 먹은 물고기를 eatenFish queue 에 저장한다. 5. eatenFish 가 비어 있을 경우 현재까지.. [백준][코틀린][16954] 움직이는 미로 탈출 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 풀이 1. 벽돌 정보를 wall 배열에 저장한다. 2. (7, 0) 을 시작으로 하는 bfs 탐색을 수행한다. 3. 이때 같은 Level 의 Queue 를 순회하고 난 뒤 벽이 이동되기 때문에 새로운 벽의 위치에 대한 BFS 를 수행하는 것으로 간주한다. 4. 그러므로 방문배열을 확인하는 visit 배열도 Level 이 변경될 때 새롭게 초기화해서 방문 배열을 사용한다. 5. 마지.. [백준][코틀린][16946] 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제 풀이 1. 주어진 문제를 전체 탐색을 하면서 벽을 하나씩 부수고 BFS 를 수행할 경우 시간 초과가 발생한다. O(N^2 * M^2) 2. BFS 를 수행할 때 이동이 가능한 영역(0)에 대해서 그룹화하여 각 그룹의 개수를 저장한다. 3. 각 그룹의 개수를 저장하는 groupMap 을 선언한다. 4. 결과를 출력한다. 이때 N, M 만큼 탐색하여 map[X][Y] 가 1.. [백준][코틀린][16933] 벽 부수고 이동하기 3 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 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. BOJ14442 번에서 낮과 밤의 조건이 추가된 문제이다. 2. 처음 접근시 BOJ14442 에서 방문 여부를 확인하는 3중 visit 배열에서 마지막에 낮/밤을 확인하는 배열을 추가하여 4중 배열로 선언했다. 3. 4중 배열로 선언할 경우 결과가 메모리 초과가 발생한다. 4. 3중 배열로 선언하고 낮과 밤에 대한 조건에 대해서 벽을 만나고 밤일.. 이전 1 2 3 4 다음
