2022/BaekJoon_알고리즘(17)
-
BFS - 숨바꼭질 [1697번]
쉬운줄 알았던데 생각보다 마음대로 풀리지 않아서 상당히 애먹었던 문제이다. 처음에는 아래와 같이 풀이를 했으나 무한루프에 빠지는 현상을 발견했다. 왜그런건지 궁금한데... 일단 추정상 not in 으로 리스트안에 값을 찾는 로직이 인덱싱하는 것보다 시간복잡도가 더 커서 그런것이라고 생각이 든다. # 수빈의 현재 점 = N, 동생의 점 = K # 위치가 X일때 걷는다면 1초 후에 X-1, X+1로 이동 # 순간이동인 경우에는 1초 후에 2*X로 이동 from collections import deque N, K = map(int, input().split()) time = 0 q = deque([(N, time)]) visited = [N] while q: x, t = q.popleft() if x == ..
2022.07.15 -
BFS - 단지번호붙이기 [2667번]
Queue 를 이용한 BFS로 풀이한 문제이다. from collections import deque N = int(input()) graph = []; visited = [] for _ in range(N): tmp = list(map(int, input())) graph.append(tmp) visited.append(list(map(lambda x : x == 1, tmp))) result = [] dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1] for i in range(N): for j in range(N): if graph[i][j] == 1 and visited[i][j] == True: q = deque([(i, j)]) num = 1 visited[i][j] = Fa..
2022.07.14 -
BFS - 미로 탐색 [2178번]
BFS보다는 DFS로 풀이하는게 직관적이다 보니, BFS에 대한 풀이가 아직은 익숙하지 않다... 휴..이제 좀 열심히 해야지 ㅜㅜ 어쨌든 이번에도 역시나 DFS로 풀이를 했는데 시간초과가 났다... 해당 풀이는 아래와 같다. def dfs(loc, curTime): global minTime if loc == [N-1, M-1]: minTime = min(minTime, curTime) return chk = False for i in range(4): nx = loc[0]+dx[i]; ny = loc[1]+dy[i] if 0
2022.07.14 -
DFS - 연결 요소의 개수[11724번]
def dfs(idx): if idx in visited: return visited.append(idx) for nextIdx in range(1, len(graph[idx])): if(graph[idx][nextIdx] == 1) and (nextIdx not in visited): dfs(nextIdx) import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N, M = map(int, input().split()) graph = [[0]*(N+1) for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 ..
2022.04.18 -
DFS - DFS와BFS[1260번]
def DFS(loc): visited.append(loc) for idx in range(1, len(graph[loc])): if len(visited) == n: return elif graph[loc][idx] == 1 and idx not in visited: loc = idx DFS(loc) def BFS(loc): queue = [loc] visited2.append(loc) while queue: curCheck = queue.pop(0) for idx in range(1, len(graph[curCheck])): if len(visited2) == n: return elif graph[curCheck][idx] == 1 and (idx not in visited2) and (idx not..
2022.04.17 -
DFS - 바이러스[2606번]
def dfs(i): for idx in range(1, len(graph[i])): if graph[i][idx] == 1 and idx not in visited: visited.append(idx) dfs(idx) n = int(input()) m = int(input()) graph = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 visited = [1] dfs(1) print(len(visited)-1) 해당 문제는 DFS 문제로 회귀함수를 이용해 1번을 시작으로 연결된 컴퓨터들을 visited로 기록함으로써 구할 수 있다. -> 1번..
2022.04.09