[Python/파이썬] 백준 9466 - 텀 프로젝트

문제 설명 입출력 예제 풀이 코드 위 예시를 그림으로 표현하면 다음과 같다. 4, 6, 7은 하나의 프로젝트 팀, 싸이클을 이루고, 3은 자기 자신을 선택해 자기 자신만 프로젝트 팀에 속한다. 총 학생의 수는 7명이므로 프로젝트 팀을 이루고 있는 (3) 그룹과 (4, 6, 7)을 빼면 어느 프로젝트 팀에도 속하지 않는 학생 수는 3이 된다. 정답 코드 import sys sys.setrecursionlimit(10 ** 8) input = sys.stdin.readline def dfs(start): global cnt visited[start] = True route.append(start) next = graph[start] if visited[next]: # 사이클이 되는 팀을 뺌 if next i..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 5. 18.
• textsms

[Python/파이썬] 백준 1068 - 트리

문제 설명 입력과 출력 입출력 예제 # 입력 5 -1 0 0 1 1 2 # 출력 2 풀이 코드 정답 코드 import sys input = sys.stdin.readline n = int(input()) tree = list(map(int, input().split())) delete = int(input()) def dfs(del_node): tree[del_node] = -10 # 의미없는 숫자를 부여해 제거함을 의미 for i in range(n): if del_node == tree[i]: # tree[i]가 del_node의 자식이면 재귀를 통해 삭제 dfs(i) dfs(delete) cnt = 0 for i in range(n): if tree[i] != -10 and i not in tree..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 5. 18.
• textsms

[Python/파이썬] 백준 1167 - 트리의 지름 (DFS / BFS)

문제 설명 입출력 예제 # 입력 5 1 3 2 -1 2 4 4 -1 3 1 2 4 3 -1 4 2 4 3 3 5 6 -1 5 4 6 -1 # 출력 11 풀이 코드 이전 포스팅한 백준 1967 트리의 지름 문제와 별 차이가 없습니다. 주어진 입력값으로 그래프를 초기화하는 방법만 다를 뿐입니다. 트리의 지름을 구하는 방법은 다음과 같습니다. 1. 시작 정점에서 임의의 정점까지의 거리를 구하여 가장 먼 거리를 구합니다. 2. 1에서 찾은 가장 먼 거리를 시작 지점으로 하여 다시 한번 가장 긴 거리를 찾습니다. 정답 코드 (DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 9) V = int(input()) graph = [[] for..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 5. 17.
• textsms

[Python/파이썬] 백준 1967 - 트리의 지름 (DFS / BFS)

문제 설명 입력과 출력 입출력 예제 # 입력 12 1 2 3 1 3 2 2 4 5 3 5 11 3 6 9 4 7 1 4 8 7 5 9 15 5 10 4 6 11 6 6 12 10 # 출력 45 풀이 코드 트리의 지름을 구하는 문제로, 가장 긴 이동 경로를 갖는 구간을 의미합니다. 트리의 지름을 구하는 방법은 다음과 같습니다. 1. 시작 정점에서 임의의 정점까지의 거리를 구하여 가장 먼 거리를 구합니다. 2. 1에서 찾은 가장 먼 거리를 시작 지점으로 하여 다시 한번 가장 긴 거리를 찾습니다. 정답 코드 (DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) n = int(input()) tree = [[] for _ in rang..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 5. 17.
• textsms

[Java/자바] 프로그래머스 Lv2 - 소수 찾기 (완전탐색/DFS)

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbers return "17" 3 "011" 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 2. 9.
• textsms

[Java/자바] 프로그래머스 Lv2 - 피로도 (완전탐색/dfs)

문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 1. 29.
• textsms