728x90 BFS6 [python] 프로그래머스_타겟넘버 (DFS&BFS) 문제 풀이 BFS 를 이용하여 풀 수 있다. 다음 수를 더하고 빼는 경우 두가지를 모두 큐에 넣으면서 BFS를 진행시키고 target 과 동일한 경우에 카운트해준다. 코드 from collections import deque def solution(numbers, target): answer = 0 queue = deque() n = len(numbers) queue.append([numbers[0],0]) queue.append([-1*numbers[0],0]) while queue: temp, idx = queue.popleft() idx += 1 if idx < n: queue.append([temp+numbers[idx], idx]) queue.append([temp-numbers[idx], id.. 2022. 2. 6. [python] 프로그래머스_단어변환 (DFS&BFS) 문제 풀이 BFS 로 풀 수 있고, 현재 단어와 words 중에 단어 하나만 다른 경우에 해당 words 를 방문하고 카운트해준다. 그렇게 반복하다가 현재 단어가 target 단어와 같아 지는 순간 BFS 종료하고 카운트한 수를 리턴해준다. 코드 def bfs(begin, target, words, visited): count = 0 stack = [(begin, 0)] while stack: cur, depth = stack.pop() if cur == target: # target에 도달했으면 depth 리턴 return depth for i in range(len(words)): if visited[i] == True: # 이미 지나쳤던 words 이면 패스 continue cnt = 0 for a.. 2022. 2. 6. [python] 프로그래머스_네트워크 (DFS&BFS) 문제 풀이 모든 컴퓨터를 돌면서 방문 안한 위치에 방문하여 DFS를 수행하여 풀 수 있다. 하나의 DFS가 종료되면 +1 해서 네트워크 수를 계산하고, DFS 함수는 해당 위치를 방문처리하고 모든 컴퓨터를 for문으로 확인하면서 자기 자신이 아니고 연결되어 있는 경우 그리고 방문을 안한 경우에 DFS로 방문처리한다. 코드 def solution(n, computers): answer = 0 visited = [False]*n # 컴퓨터 개수 만큼 for com in range(n): # 각 컴퓨터를 돌면서 방문 안했으면 DFS if visited[com] == False : DFS(n, computers, com, visited) answer +=1 # 연결된 하나의 네트워크 +1 return answe.. 2022. 2. 6. [python] 백준18405_경쟁적 전염 (DFS&BFS) 문제 풀이 BFS를 이용하여 풀 수 있고, 각 바이러스가 낮은 번호부터 증식하기 때문에 초기에 큐에 원소를 삽입할 때 낮은 바이러스의 번호부터 삽입해야 한다. 큐에서 낮은 바이러스 번호부터 pop하여 상하좌우로 바이러스 번식시키고, 번식된 위치를 다시 큐에 넣고, 원하는 시간이 될 때까지 반복한다. 코드 from collections import deque n, k = map(int,input().split()) graph = [] # 전체 보드 정보를 담는 리스트 data = [] # 바이러스에 대한 정보를 담는 리스트 for i in range(n): # 보드 정보를 한 줄 단위로 입력 graph.append(list(map(int, input().split()))) for j in range(n):.. 2022. 2. 6. [python] 백준18352_특정 거리의 도시 찾기 (DFS&BFS) 문제 풀이 '모든 도로의 거리는 1'이라는 조건 덕분에 BFS를 이용하여 해결할 수 있다. 코드 from collections import deque n,m,k,x = map(int,input().split()) # 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호 graph = [[] for _ in range(n+1)] # 도시 개수 만큼 graph 리스트 생성 for _ in range(m): # 도로 정보 입력받아서 graph 에 정장 a, b = map(int,input().split()) graph[a].append(b) distance = [-1]*(n+1) # 모든 거리는 -1 로 초기화 distance[x] = 0 # 출발 도시 거리는 0 q = deque([x]) # 출발 도시를 큐.. 2022. 2. 6. [BFS] 미로 탈출 - 문제 주인공은 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 주인공의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0 없는 부분은 1로 표시되어 있다. 이 때 주인공이 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하시오. 단 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. - 해설 BSF로 풀 수 있는 문제. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 그러므로 (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. from collections import deque n,m = map(int, input().split()) # 2차.. 2021. 5. 17. 이전 1 다음 728x90
