Beelog

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제는 위와 같으며 이 경우는 일반적인 DFS 를 통해 연결 요소를 확인하고 그 수를 세면 해결할 수 있는 문제입니다. 파이썬 코드는 다음과 같습니다. from sys import stdin # 일반적인 DFS 수행 (연결 요소 찾기) def dfs(start): queue = [start] while queue: node = queue.pop() ..

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/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이 아닌 경우)는 해당 위치에 지금까지 방문했던 값을 반환하고 - 두 가지 경우가 아닌 경우는 상하좌우로 이동할 수 있는지 확인하고 이동하려는 위치의 ..