본문 바로가기

dfs35

[프로그래머스 Lv.2] 타겟 넘버 # BFS from collections import deque def solution(numbers, target): answer = 0 queue = deque() queue.append((numbers[0],0)) queue.append((-numbers[0],0)) while queue: v, index = queue.popleft() index += 1 if index < len(numbers): queue.append((v+numbers[index],index)) queue.append((v-numbers[index],index)) else: if v == target: answer += 1 return answer #DFS def solution(numbers, target): global .. 2023. 8. 2.
[프로그래머스 Lv.3] 네트워크 def solution(n, computers): answer = 0 graph = [[] for i in range(n)] visited = [False]*n for i,row in enumerate(computers): for j,value in enumerate(row): if i != j and value == 1: graph[j].append(i) def dfs(n): if visited[n]: return False visited[n] = True for i in graph[n]: if not visited[i]: dfs(i) return True for i in range(n): if dfs(i): answer += 1 return answer 이번 문제는 컴퓨터의 개수 n과 연결에 대한 정.. 2023. 7. 31.
[프로그래머스 Lv.3] 여행경로 def solution(tickets): answer = [] graph = {} for i in range(len(tickets)): if tickets[i][0] not in graph: graph[tickets[i][0]] = [tickets[i][1]] else: graph[tickets[i][0]].append(tickets[i][1]) graph[tickets[i][0]].sort(reverse=True) print(graph) stack = ["ICN"] while stack: top = stack[-1] if top not in graph or not graph[top]: print("stack pop : ",stack[-1]) answer.append(stack.pop()) else: p.. 2023. 7. 30.
[HackerRank] Count Luck def countLuck(matrix, k): row = len(matrix) col = len(matrix[0]) nx = [-1,1,0,0] ny = [0,0,-1,1] start_x, start_y = 0, 0 count = 0 graph = [] for i in range(row): graph.append(list(matrix[i])) for i in range(row): for j in range(col): if graph[i][j] == 'M': start_x, start_y = i, j # Write your code here def dfs(area, x, y): # visited[x][y] = True if area[x][y] == '*': return True direct_count = .. 2023. 5. 19.
[백준 14502번] 연구소 import copy def dfs(graph, x, y): if graph[x][y] != 2: return for i in range(4): temp_x = x + nx[i] temp_y = y + ny[i] if temp_x >=0 and temp_x =0 and temp_y < m: if graph[temp_x][temp_y] == 0: graph[temp_x][temp_y] = 2 dfs(graph,temp_x,temp_y) def count_safe_area(graph): count = 0 for i in range(n): for j in range(m): if graph[i][j] == 0: count += 1 return count n, m = map(int,in.. 2023. 5. 10.
[백준 1520번] 내리막 길 import sys sys.setrecursionlimit(50000000); m, n = map(int,input().split()) area = [list(map(int,input().split())) for _ in range(m)] dp = [[-1]*n for _ in range(m)] nx, ny = [-1,1,0,0], [0,0,-1,1] def dfs(x,y): # 도착 지점에 도달하면 1 리턴 if x == (m-1) and y == (n-1): return 1 # 이미 방문한 길이라면 경우의 수를 구하지 않고 해당 위치에서 출발하는 경우의 수 리턴 if dp[x][y] != -1: return dp[x][y] way_count = 0 for i in range(4): temp_x = x.. 2023. 4. 10.

티스토리툴바