본문 바로가기
728x90

dfs6

[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] 백준14502_연구소 (DFS&BFS) 문제 풀이 DFS로 바이러스 퍼지게 하는 함수와 현재 맵에서 안전영역을 구하는 함수를 만들어 두고, 빈 공간에 울타리를 치는 모든 경우의 수를 DFS로 찾으면서 매번 안전영역의 크기를 검사한다. 코드 n, m = map(int,input().split()) data = [] # 초기 맵 리스트 temp = [[0]*m for _ in range(n)] for _ in range(n): data.append(list(map(int,input().split()))) # 서남동북 dx = [-1,0,1,0] dy = [0,1,0,-1] result = 0 # DFS로 바이러스 퍼지게 하기 def virus(x,y): for i in range(4): nx = x + dx[i] ny = y + dy[i] # 상.. 2022. 2. 6.
[DFS] 음료수 얼려 먹기 - 문제 NxM 크기의 얼음 틀이 있고 구멍이 뚫려 있는 부분을 0, 칸막이가 존재하는 부분을 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결된 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. ex) 00110 00011 11111 00000 -> 아이스크림 3개 생성 - 해설 DFS 로 해결할 수 있는 문제 1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문 2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면 연결된 모든 지점을 방문할 수 있다. 3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 .. 2021. 5. 17.
728x90

티스토리툴바