Beelog

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제는 위와 같으며, 우선순위 큐와 BFS 를 통해 문제를 해결할 수 있습니다. 먼저 주어진 미로를 이차원 배열에 저장하고, 출발점(0,0)을 우선순위 큐에 추가합니다. 이때 [현재 위치까지 지나온 위치 수(현재 위치 포함), 현재 위치의 x 값, 현재 위치의 y 값] 형태로 데이터를 저장합니다. 현재 위치까지 지나온 위치 수를 기준으로 우선순위 큐에 데이터를 저장하게 되면 같은 위치를 확인하게 되는 경우 해당 위치까지 방문한 최소 위치 수를..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제는 위와 같으며, 이 문제는 우선순위 큐와 BFS 를 사용하여 해결하였습니다. 먼저 토마토의 위치를 이차원 배열로 저장하고, 우선순위 큐를 생성하여 처음부터 익어있는 토마토를 우선 저장합니다. 우선순위 큐에 토마토를 저장할 때, [익는데 걸리는 일수, 토마토의 x 좌표, 토마토의 y 좌표] 형태로 데이터를 저장합니다. 이렇게 익는데 걸리는 일수를 기준으로 우선순위 큐에 데이터를 저장하게 되면..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제는 위와 같으며, 모든 아파트를 방문하였는지 확인하고 방문하지 않은 경우 주변 연관된 아파트들의 수를 확인하는 DFS 방식으로 문제를 해결할 수 있습니다. 예제를 살펴보면 아파트 위치와 방문했는지 여부를 확인하는 2차원 배열 2개를 생성합니다. 이후, 아파트 위치를 순차적으로 모두 확인하여 아파트가 있으면서 아직 아파트를 확인하지 않은 경우 dfs 메소드를 수행합니다. 이 dfs 메소드에서는 우선 현재 위치의..

programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 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 를 통해 해결할 수 있습니다. 시작지점과 끝 지점이 있는 것이 아니기 때문에 전체 컬러링북의 크기인 m x n (1 = 0 && ny < nn) { // 컬러링 북 범위 내에서 if (visited[nx][ny] == 0 && pictures[x][y] == pictures[nx][ny]) { // 방문한 적이 없으면서 같은 색으로 칠해진 ..

www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제는 위와 같으며, 지점의 높이를 이차원 배열로 저장하고 해당 배열과 동일하게 특정 위치를 방문했는지 알 수 있는 배열을 생성한 뒤 -1로 초기화 합니다. 방문했던 위치가 - 도착 지점과 같은 경우 1을 반환하고 - 한번이라도 방문한 적이 있는 경우(저장된 값이 -1이 아닌 경우)는 해당 위치에 지금까지 방문했던 값을 반환하고 - 두 가지 경우가 아닌 경우는 상하좌우로 이동할 수 있는지 확인하고 이동하려는 위치의 ..