일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- PYTHON
- CSS
- 리눅스
- 프로그래밍
- 프로그래머스
- DFS
- dp
- nlp
- BFS
- AI
- 브루트포스
- 백준
- OS
- linux
- 코딩 테스트
- 동적프로그래밍
- 동적 프로그래밍
- 킥스타트
- 그래프
- 딥러닝
- kick start
- 네트워크
- 코딩
- 코딩테스트
- 알고리즘
- google coding competition
- 구글 킥스타트
- 운영체제
- 파이썬
- 순열
- Today
- Total
목록BFS (21)
오뚝이개발자
문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 � www.acmicpc.net 생각의 흐름 사실 혼자 힘으로 풀지 못해 블로그를 많이 참고해서 구현하였다. 참고한 블로그는 https://rebas.kr/770이다. 위 블로그에 드러나지 않은 부분을 설명하겠다. bfs함수의 for문 안에서 '.'인 경우 appendleft를 해주고 '#'인 경우 그냥 append를 해주는데 이유는 '.'인 경우를 우선적으로 처리하도록 하기 위함이다. 왜냐하면 '.'와 연결된 경우는 문을 부수지 ..
문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 생각의 흐름 수빈이가 X에 있을 때 이동가능한 경우의 수는 X-1, X+1, 2X의 세가지이다. 가능한 경우는 이 세가지이므로 수빈이의 위치를 q에 넣고 이들을 pop하면서 BFS로 탐색을 해주면 된다. 이 때, pop을 했을 때 원소가 K와 같은 값이면 탐색을 종료한다. 방문을 체크하기 위해서는 visit이라는 1차원 리스트를 사용하였다. 리스트에는 ..
문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 생각의 흐름 메모리 제한이 심한 문제이다. 따라서 2차원 리스트 그대로를 이용해 문제를 풀기에는 무리가 있다. 메모리 제한을 해결하기 위해선 저장하는 방식을 바꾸어야 하는데 주어진 예시에서 0을 9로 바꿔주고 이를 int형으로 저장한다. 예를 들어 예제1의 경우 193425786이 된다. 위와 같이 저장하면 특정한 "상태"를 나타낼 수 있는데 이 상태에 대한 value 값으로 이동 횟수를 매칭시켜 저장해야 한다. 이를 위해 dictionary 구조를 사용한다. 즉, k..
문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 생각의 흐름 편의상 물통을 각각 x,y,z라고 하자. 물이 담겨 있는 것을 "특정한 상태"라고 바라보자. 그러면 이 특정상태는 x,y에 ..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 생각의 흐름 정말 너무 미운 문제다...ㅜㅜ 이거때문에 코딩 그만둘까 생각함... 진짜 꿈에서도 이 문제 푸는 꿈 꾼 듯...정답률이 ..
문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 생각의 흐름 전형적인 DFS 문제이다. 문제의 요점은 A-B, B-C, C-D, D-E인 친구관계가 존재하는지를 조사하는 것이다. adjacent list를 이용하여 연결관계에 대한 정보를 저장하고 시작점을 vertex 0부터 n-1까지 돌아가면서 dfs를 사용하여 depth가 4이상이 되는 subgraph가 존재하는지를 판별하면 된다. 코드 n, m = map(int, input().split()) adj_lst = [[] for i in range(n)] for i in range(m): a,..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 생각의 흐름 일반적인 BFS 문제이다. 처음에 행렬을 하나씩 돌면서 1인 곳의 위치 (x,y)를 q에 넣어주고, 여기서 하나씩 빼서 ..
문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 생각의 흐름 결국 최종적으로는 화면에 n개의 이모티콘이 있어야 하는데 이 때, 클립보드에 있는 이모티콘의 갯수가 0~n-1개 일..