일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 순열
- 딥러닝
- 코딩
- google coding competition
- dp
- 동적프로그래밍
- AI
- DFS
- PYTHON
- 네트워크
- OS
- 운영체제
- nlp
- 그래프
- 백준
- 프로그래머스
- 코딩테스트
- 리눅스
- linux
- 파이썬
- 코딩 테스트
- BFS
- 프로그래밍
- CSS
- 브루트포스
- 알고리즘
- 구글 킥스타트
- 동적 프로그래밍
- 킥스타트
- kick start
- Today
- Total
목록DFS (14)
오뚝이개발자
문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 생각의 흐름 이전에 포스팅했던 알고스팟과 유사한 문제이다. 차이점은 2가지이다. 시작점과 끝점의 칸 수를 포함하여 계산한다는 점 알고스팟의 경우 칸의 수가 1인 경우와 0인 경우 모두 이동이 가능했지만 본 문제의 경우 1인 경우에만 이동이 가능하다는 점 코드 from queue import PriorityQueue as pq def dijkstra(): heap = pq() heap.put((1, (0, 0))) crush..
문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 생각의 흐름 매우 전형적인 DFS, BFS 문제이므로 코드로 설명을 대신한다. 코드 import sys def dfs(cnt, x, y, arr): arr[x..
문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 생각의 흐름 (0,0)을 시작점으로 보고 (n-1, m-1)칸, 다시말해 우측 맨 하단의 칸을 도착지점으로 보고 최단경로를 찾기 위한 다익스트라 알고리즘을 적용하면 된다. 이 때, 1이 있는 곳으로 이동할 때에는 벽을 부숴야 하기 때문에 가중치가 1인 것으로, 0인 곳은 가중치가 0인 것으로 보면 된다. 어려운 부분은 최..
문제 https://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 생각의 흐름 adjacent matrix를 만들어 dfs로 탐색한다. 깨달은 점 adjacent list를 만들어 dfs로 탐색하는 방법도 있다.(아래 코드를 첨부한다. 출처 : https://home-body.tistory.com/287) 코드 방법 1(adjacent matrix 이용) import sys N, M = ..
문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 생각의 흐름 인접한 곳들을 탐색하여 그룹을 짓는 문제이다. 특이한 점은 일반적인 상하좌우 이외에도 대각선 4곳까지도 인접한 영역으로 ..
문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 www.acmicpc.net 생각의 흐름 이전에 포스팅한 연산자 끼워넣기와의 차이점은 연산자의 갯수가 많아졌다는 점이다. 동일한 방법으로 짜도..