KBW's cosmos

처음에는 백트래킹으로 접근하려고 했다. """ 1. 아이디어 - 백트래킹으로 탐색하며 벽을 뚫을 때와 안뚫을 떄를 구분하여 전체 가지수를 탐색한다. 2. 시간 복잡도 - O(N * M) : 1000 * 1000 = 1,000,000 -> 가능 3. 변수 - N, M : int - map : int[][] - visit : bool[][] """ import sys sys.setrecursionlimit(10 ** 6) INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) map = [list(map(int, input().rstrip())) for _ in range(N)] visit = [[False] * M for ..

from collections import deque def solution(begin, target, words): answer = 0 wordsNum = len(words) visited = [0 for _ in range(wordsNum)] queue = deque() queue.append(begin) while queue: popWord = queue.popleft() if popWord == target: answer = visited[words.index(target)] break for i in range(wordsNum): if visited[i] == 0: # 아직 방문하지 않은 단어만 방문함 check = 0 for j in range(len(popWord)): if popWord[j..

경로를 표현해야해서 처음에는 DFS로 탐색해야하나..? 생각했다 하지만 BFS로도 충분히 해결할 수 있었다. 경로에 대한 배열을 따로 만들어 최단경로에 대한 값을 저장하며 해결하는 것이다. # 아래는 따로 path 배열을 안만들고 파라매터로 받아 처리한건데 시간초과 나온다... # 왜 시간초과가 나올까..? import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) road = [0] * 100001 queue = deque() queue.append([N]) road[N] = 1 while queue: pathList = queue.popleft() popN = pathList[-1..

기존 숨바꼭질 문제에서는 모든 가중치가 1이었다. 이 문제의 차이점은 순간이동하는 경우는 0으로 가중치가 다르다는 것이다. 순간이동은 0초가 걸리고 걷기는 1초가 걸리므로 큐를 2개로 나눠 구현하면 된다. 이때 양방향 큐인 deque를 활용하면 별도의 큐를 더 생성하지 않고 구현할 수 있다. 순간이동하는 경우는 appendleft로 맨앞에 추가해주고 걷는 경우는 append로 뒤에 추가해주면 된다. import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) road = [0] * 100001 queue = deque() queue.append(N) road[N] = 1 while qu..

""" 1. 아이디어 가장 빠른 시간을 출력하고 '방법의 가짓수'도 출력해야하므로 dfs로 탐색해야한다. 최대 수는 동생 위치에서 수빈이의 위치를 뺀 값이고 해당 값에 도달하면 탐색을 마쳐야한다. (그때까지 찾아도 못찾았다는건 최단거리 탐색에 실패한 트리가지인거니까) dfs로 탐색했을 때 동생이 있는 점 K에 도달할 때 도달하는데 걸린 횟수를 저장한다. 그리고 다음에 또 도달하면 둘을 비교해 더 큰 값을 저장한다. 만약 같다면 같은 도달 시간 횟수를 체크한다. bfs로 탐색한다. visited 배열에 걸린 시간을 체크해서 적어두는데 이미 시간이 적힌 배열칸에 다시 접근하기 위해서 or 연산자를 이용해 visited[nextX] == visited[popX] + 1 를 추가한다. 2. 시간복잡도 - 3. ..

1. 아이디어 bfs로 queue를 만들고 1인 지점부터 시작해서 queue에 넣고 pop하길 반복한다. 처음 시작할 때 1인 지점을 몽땅 queue에 넣어두고 시작한다. 처음 1인 곳이 여러곳일 수 있다. 그래서 queue에 있는걸 다 처리하게 해야한다. 따로 if문을 두고 break하지 않는다. 마지막에 이중포문 돌리면서 익지못한 토마토(0)가 있는지 확인 없다면 가장 큰 숫자 출력 2. 시간복잡도 - BFS : O(V + E) - V : 1000 * 1000 - E : 4 * 1000 * 1000 - V + E : 5 * 1000 * 1000 = 5e6 (5백만) - 이중포문 : O(NM) - NM : 1000 * 1000 - 전체 시간복잡도 : O(6NM) = 6e6 (6백만) - 2억보다 작으므..

정점과 간선은 Graph에서 나오는 개념들이다. 정점은 흔히 Vertex라고 부르며 간선은 Edge라고 부른다. 전체 풀이 ↓ import sys from collections import deque N, M, V = map(int, sys.stdin.readline().rstrip().split()) graph = [[0] * (N + 1) for _ in range(N+1)] DFS_visited = [False] * (N + 1) BFS_visited = [False] * (N + 1) for _ in range(M): x, y = map(int, sys.stdin.readline().rstrip().split()) graph[x][y] = 1 graph[y][x] = 1 def dfs(V): DF..