클라우드 낚시꾼

문제 해결 과정 이 문제는 단순 BFS 문제였고, 인접 정점을 내림차순으로 정렬하는 조건이 중요했다. 문제가 쉬움에도 불구하고 나는 계속 답은 맞는데 시간 초과 문제가 발생했다. 그 이유는 아래와 같다. 시간 초과가 발생했던 이유 원래 필자는 그래프에 정보를 추가하면서 인접 정점을 정렬하였다. 그래서 정렬 과정이 2번 일어났고 이것이 시간 초과가 발생했던 주된 이유였다. 시간 초과 문제를 해결하기 위해 기존의 정렬 코드를 없애고 그래프 정렬을 위한 for문을 작성하여 정렬과정을 수행했다. 그 결과 정렬 코드의 시간 복잡도가 O(2n)에서 O(n)으로 감소하였다. 전체 코드 import sys from collections import deque input = sys.stdin.readline m,n,r ..

제한 조건과 설계 미로 문제처럼 M*N 격자 그래프 문제이므로 BFS를 사용한다. 1은 검은색 격자이기에 전류가 잘 통하지 않고, 0은 흰색 격자로 전류가 잘 통한다. 0행에서 M-1행에 도달하는 경로가 있는 지를 물어보는 문제다. 자연어 알고리즘 정보를 입력 받고 그래프를 생성한다. 0행에서 값이 0인 좌표가 시작 지점이다. 이 지점들을 starts 리스트에 저장한다. starts 중 한 지점으로 BFS 탐색을 시도 했을 때 m-1 행에 도달하면 YES를 출력하고 프로그램을 종료한다. starts의 모든 지점을 시작 지점으로 BFS를 반복한다. 3번에서 YES를 출력하고 종료되지 않았다면 NO를 출력하고 프로그램을 종료한다. 코드 import sys from collections import deque..

제한 조건과 설계 시간 제한이 2초지만 노드가 30만개라서 좀 불안하다. 방향 그래프다. 시작 노드로부터 모든 각 노드의 거리를 구하는 것이므로 BFS가 좋아보인다. 자연어 알고리즘 정보를 입력 받아 그래프를 생성한다. 시작 정점으로 BFS 탐색을 시도한다. queue에서 front 노드를 dequeue한다. dequeue된 노드의 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면 queue에 인접 노드를 enqueue 한다. 시작 노드로부터 인접 노드의 거리 = 시작 노드로부터 이전 노드(dequeue된 노드)의 거리 + 1 queue가 빌 때까지 위의 과정을 반복한다. 선형 탐색으로 nodes_dist에서 요소 값이 k(거리)인 index를 ans리스트에 append 한다. 답에 해당하는 노드들을..

제한 조건과 설계 1. W와 H는 50보다 작다. -> MAX 2500 그래프 2. DFS로 2000번 이상 탐색 시 Recursion Error 발생될 수 있기에 BFS 선택 3. 시간 제한 1초, 메모리 제한 128MB -> 엄격한 제한이므로 Queue 방문 처리 필수 자연어 알고리즘과 코드 1. 그래프 입력을 받는다. 2. 그래프를 BFS로 탐색한다. 탐색 지점이 0 이면 -> continue 탐색 지점이 1 이면 -> 그 지점을 시작 지점으로 삼아 queue에 enqueue하고 BFS 탐색을 시작 land를 1증가시킨다. Queue에서 dequeue 한다. for문을 이용해 dequeue 된 지점에서 상,하,좌,우 + 왼쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 위 대각선, 오른쪽 아래 대각선으로..

문제 해석 미로 찾기 문제와 비슷하다. 1 ≤ R, C ≤ 500 이므로 최대 250000 크기의 그래프가 생성될 수 있다. 시간 제한은 2초이므로 O(N^2) 이하가 적절해 보인다. 양(S)은 가만히 있고, 늑대(W)가 움짇인다. 늑대가 양을 잡아 먹는 그 순간의 지점에 울타리 D를 설치 해야 한다. 스페셜 저지 문제이므로 쉽게 생각하면, 모든 빈 공간에 울타리 D를 설치하면 된다. 늑대와 양이 붙어 있는 그래프는 어떤 수를 써도 늑대를 막을 수 없다. 자연어 알고리즘과 코드 그래프 정보를 입력 받는다. 그래프 요소에 차례 차례 접근한다. if 요소 빈 공간 -> 빈 공간에 울타리를 친다. if 요소가 늑대 -> 상,하,좌,우로 양 있는지 확인한다. 만약, if 양이 있다. -> 0을 출력하고 즉시 종..

시간 복잡도와 공간 복잡도 N과 M의 최댓값은 100이기에 미로의 최대 크기는 10000이다. 미로 탐색을 10000번 하더라도 1초에 2000만번 연산이 가능한 Python3에 10000번의 연산은 그리 무거운 연산이 아니다. 시간 복잡도는 O(n^3) 이상만 아니면 될 거라고 생각했다. 자연어 알고리즘과 코드 참고) 2차원 리스트 graph의 요소 값이 1이면 처음 방문한 좌표, 0이면 벽, 음수면 맵 범위 밖이다. 만약, graph의 좌표 값이 2이상 양수면 시작 점으로부터 그 좌표까지의 거리를 의미한다. 1. 미로 그래프와 상하좌우 방향을 지정하는 리스트를 생성한다. 2. 시작 지점을 0,0으로 설정하여 미로 탐색을 시작한다. 3. queue에 시작 지점 좌표를 append 한다. 4. qeueu..

시간 복잡도와 공간 복잡도 문제 조건에 따르면 최대 노드의 개수는 10000 개, 최대 간선의 개수는 100000 개였다. 최악의 시간 복잡도가 O(110000)이고 시간 제한이 5초라서 시간 복잡도는 여유롭다는 판단을 내렸다. 하지만, 노드랑 간선의 개수가 1000개를 넘어가기에 DFS로 구현하면 RecursionError가 발생하기에 BFS로 구현하기로 마음먹었다. 자연어 알고리즘과 코드 1. 방향 그래프를 만든다. 2. 시작 노드를 1~n 순차적으로 설정하여 BFS 탐색을 한다. 3. 시작 노드를 x으로 설정하여 BFS 탐색을 할 때, 탐색된 노드의 개수가 해킹할 수 있는 컴터의 개수이다. 4. 3번의 정보를 리스트 a에 담고 max를 찾는다. 5. 리스트a에서 max를 가진 요소의 인덱스 탐색하고..

시간 복잡도와 공간 복잡도(런타임 에러 RecursionError) BFS, DFS의 시간 복잡도는 O(V+E)이다. 노드의 개수는 최대 100000개이고 간선의 개수는 99999개이기에 O(199999)가 최악의 시간 복잡도이다. Python3는 1초에 2000만번 연산이 가능하기에 O(199999)가 문제가 되지 않아 보이지만, Python3 기준 최대 재귀 깊이는 1000이기에 199999번 재귀호출 할 경우 RecursionError가 발생한다. 그래서 재귀 호출을 이용하는 DFS보다는 반복문 베이스인 BFS를 이용해서 이 문제를 해결해야 한다. 자연어 알고리즘과 코드 1. 입력을 받고 조건대로 Graph와 방문 테이블을 생성한다. 2. bfs 함수를 정의한다. 3. bfs 함수 내부에 부모 노드..