본문 바로가기

전체 글107

[BFS] 미로에서 길찾기 게임 BFS 사용하기 가장 가까운 칸들부터 탐색하며 갈 수 있는지 판단하기 때문에 현재 있는 위치의 동서남북을 탐색한다면 괴물이 있는 곳은 피할 수 있을 거 같다. 큐를 사용하여 주변을 탐색을 하는데 (N,M)까지 가야하므로 오/아/왼/위 순으로 탐색을 진행하면서 큐에 넣어야 겠다. 최소 거리 이동한 칸의 개수를 어떻게 측정? 큐에 넣을 때, bfs를 위한 좌표값만 큐에 넣는 것 이 아닌 거기까지 걸린 비용도 같이 리스트로 묶어서 넣어버리면 어떠할까 라는 아이디어 예를 들어 첫 좌표에서 동서남북을 탐색해서 큐에 넣는 주변 노드들은 모두 2랑 묶어서 큐에 넣는 방식 큐에 넣다가 만약에 N,M을 만난 경우 그 때 cnt 수를 return 하는 방식 가장 먼저 N,M에 도착했다는 것은 가장 짧은 거리로 왔다는 것과.. 2021. 9. 10.
[DFS] 틀 모양의 아이스크림 찍어내기 문제 0과 1로된 2차원 배열 모양의 아이스크림 판이 있다. 0인 부분은 뚫려 있고 1인 부분은 뚫려있지 않은 아이스크림 판이다. 이 판을 아이스크림에 올리면 모양이 나오게된다 예를 들어서 ) 00001111 00111000 111000111 처럼 판이 생겼다면 두개의 아이스크림 탄생한다 아이스크림의 개수를 구하는 알고리즘을 만들라 해결 하나의 모양을 만들려면 0들이 이어져야 한다. 이어진 0들을 찾기 위해서는 0을 하나 발견했을 때 위/오/왼/아래 방향으로 탐색하여 0이 있는지 확인하며 꼬리에 꼬리를 물고 늘어져야 한다. 단, 모양이 여러개 나올 수 있기 때문에 우리는 모든 틀 하나하나를 다 봐야한다 그러기 위해서는 visited를 만들어서 이미 방문한 노드는 다시 방문하지 않고 넘어갈 수 있도록 조치.. 2021. 8. 19.
Depth First Search 깊이 우선 탐색 알고리즘 어떤 노드에서 다른 연관있는 노드로 이동하고 이동해서 도착한 노드에서 그 노드와 연관된 노드로 이동하고 .... 꼬리 물기 식으로 어떠한 관계가 있는 노드로 끝까지 물고 늘어지는 탐색 알고리즘이라고 나는 이해했다. DFS 알고리즘이 이용하는 자료구조는 STACK stack의 용도는 되돌아가기 위해서이다. (돌아갈까바그래~) 깊이 탐색하기 위해서 낮은애들부터 정복할 건데 다 정복하면 다시 위로 올라와서 정복하지 않은 아이들을 정복해 나가야 한다. 2번 노드에서 DFS를 시작한다고 가정한다면 (여러개가 이어져 있다면 노드 번호가 가장 낮은 것부터 탐색 한다) 1번을 stack에 Push -> 3번을 stack에 Push -> 2번은 방문했으니 3번을 pop 하고 -> 되돌아와서 다시 1번이랑 연결되어 있는 .. 2021. 8. 18.
[Greedy] 큰수를 만들기 문제 배열(arry)에 들어가 있는 수를 M번 더하여 가장 큰수를 만드는 방식 단 배열의 특정 위치에 해당하는 수가 연속 K번 더해질 수는 없음 예시 ) K=3, M=5일때 5, 4, 2, 6, 7 -> 7+7+7+6+7 가장 큰수를 만드는 것이기 때문에 data들을 정렬하여 가장 큰 수를 찾는다 정렬의 경우에는 logN의 시간이 걸리는 최대 heap을 사용함 가장 큰수를 K번 더하면 더 더할 수 없으니 두번째 수를 한번 더하고 다시 가장 큰수를 더한다 즉, 가장 큰수와 두번째로 큰수를 번갈아(K번 + 1번) 더하면 됨 import sys import heapq input = sys.stdin.readline arry = [] N, M, K = map(int, input().split()) data = .. 2021. 8. 6.

티스토리툴바