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/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제는 위와 같으며, 모든 아파트를 방문하였는지 확인하고 방문하지 않은 경우 주변 연관된 아파트들의 수를 확인하는 DFS 방식으로 문제를 해결할 수 있습니다. 예제를 살펴보면 아파트 위치와 방문했는지 여부를 확인하는 2차원 배열 2개를 생성합니다. 이후, 아파트 위치를 순차적으로 모두 확인하여 아파트가 있으면서 아직 아파트를 확인하지 않은 경우 dfs 메소드를 수행합니다. 이 dfs 메소드에서는 우선 현재 위치의..
www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제는 위와 같으며, 지점의 높이를 이차원 배열로 저장하고 해당 배열과 동일하게 특정 위치를 방문했는지 알 수 있는 배열을 생성한 뒤 -1로 초기화 합니다. 방문했던 위치가 - 도착 지점과 같은 경우 1을 반환하고 - 한번이라도 방문한 적이 있는 경우(저장된 값이 -1이 아닌 경우)는 해당 위치에 지금까지 방문했던 값을 반환하고 - 두 가지 경우가 아닌 경우는 상하좌우로 이동할 수 있는지 확인하고 이동하려는 위치의 ..
www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제는 위와 같으며, 밭의 모든 위치를 확인하여 배추가 심어져 있지만 방문한 적 없는 경우 dfs 로 방문한 뒤, 한번 dfs 가 끝나면 하나의 연결 요소가 끝난 것으로 판단하여 result 를 +1 하는 방식으로 전체 연결 요소의 개수를 구하면 됩니다. 파이썬 코드는 다음과 같습니다. import sys sys.setrecursionlimit(100000) # 재귀 가능 범위 제한 해결 def dfs(now_x, now_..
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제는 위와 같으며 DFS 와 BFS 를 구현할 수 있다면 간단하게 해결할 수 있습니다. 여기서 주의할 점은 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다"는 것입니다. 먼저 DFS 는 방문이 필요한 노드를 담을 stack 과 이미 방문한 노드를 담을 queue 가 있으면 구현할 수 있고, BFS 는 방문이 필요한 노드를 담을 queue ..
- Total
- Today
- Yesterday
- java
- spring
- Dynamic Programming
- 에라토스테네스의 체
- 프로그래머스
- Algorithm
- CodeDeploy
- Baekjoon
- Combination
- 순열
- permutation
- cloudfront
- AWS
- DFS
- SWIFT
- 소수
- search
- ECR
- ionic
- sort
- CodeCommit
- 조합
- array
- map
- EC2
- CodePipeline
- programmers
- 수학
- string
- BFS
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |