깊이우선탐색 (19) 썸네일형 리스트형 [프로그래머스] 빛의 경로 사이클 https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🤔 문제분석그래프 탐색문제로 한 방향으로 들어갔다면 다음에 탐색을 할 필요가 없습니다. 다음 탐색시 똑같은 루트로 탐색되기 때문입니다.문제의 이미지를 보고 방문처리를 활용하여 문제를 해결해야겠다는 생각이 들었습니다. 한 노드에서 방문 처리해야할 조건은 8가지 인데 8가지는 아래와 같습니다.IN ( 상, 하, 좌, 우 ) 4개OUT ( 상, 하, 좌, 우) 4개문제에서 제시한 조건으로 깊이우선탐색 합니.. [백준] 2668번 : 숫자고르기 2668번: 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤔 문제분석 깊이 우선탐색으로 아래 숫자를 뽑아서 그 숫자로 이동하면서, 위쪽 집합과 아래쪽 집합이 동일할 경우 정답 리스트에 값을 추가시켜줍니다. 위쪽 집합과 아래쪽 집합이 같다는건 결국 집합을 만들 수 있다는 조건을 만족시키기 때문입니다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) nums = [int(input()) for _ in range(N)] def .. [백준] 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해당 문제는 깊이우선탐색 + 다이나믹프로그래밍 으로 문제를 해결 하였습니다. 1. end_nodes를 찾습니다. end_nodes는 루트 노드들 입니다. 2. end_nodes로 부터 시작하여 dp 테이블을 업데이트 합니다. ( 방문 가능한 노드들중 최대값으로 ) 3. dp[W] 값을 출력하여 W의 최대값을 출력합니다. T = int(input()) def dfs(node, graph, d,.. [백준] 2638번 : 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 위의 문제는 탐색의 문제로 깊이우선탐색과 너비우선 탐색으로 모두 문제를 해결 할 수 있습니다. 1. 치즈의 개수를 구한다. 개수가 0이상이라면 치즈를 녹여야 한다. 그렇지 않으면 종료한다. 2. 치즈를 녹일때 너비우선탐색 혹은 깊이우선탐색으로 녹여야할 치즈 후보를 구한다. 3. 녹여야할 치즈 후보를 현재 그래프에 적용하고, 시간을 증가한다. 4. 1~3까지 계속 반복하여 시간 최종 시.. [백준] 13023번 : ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깊이우선탐색(DFS)로 문제를 해결 하였습니다. 친구의 관계가 A->B->C->D->E와 같은 경우가 존재할경우, DFS탐색을 중지합니다. 사이클이 생기지 않도록 탐색한 친구는 또 탐색하지 않습니다. Set 자료구조를 활용하여 깊이우선 탐색을 한 친구는 Set 자료구조에 추가하여 이미 방문한 친구를 찾을때 O(1) 시간복잡도로 찾을 수 있습니다. import sys sys.setrecursionlimit(100000) N , M = map(int ,input().split()) graph = [[] f.. [백준] 9466번 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 순열 사이클 문제로 접근하여 문제를 해결하였습니다. 깊이우선 탐색으로 한 학생으로부터 선택한 팀원을 깊이우선 깊이 우선 탐색하면서 마지막 학생이 시작한 한 학생을 가르킨다면 사이클이 생기고 이 사이클이 생긴 리스트들을 결과 값에 저장합니다. 또한 자기자신이 자기자신을 뽑은경우는 자기혼자 팀원이 될 수 있습니다. cycle[cycle.index(newstudent) 자기자신의 Index로 부터 개수를 새.. [백준] 15683번 : 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 해당 문제는 완전탐색 + 깊이우선탐색 + 조합 문제로 해결 하였습니다. 1. CCTV를 하나씩 모두 다 돌려보며 사각지대의 최소값을 구합니다. 2. 해당 CCTV로부터 감시영역은 깊이우선탐색으로 탐색합니다.( 방향성이 있기 때문 ) 3. 재귀 함수를 통하여 CCTV를 하나씩 돌려보며 모든 조합을 호출 합니다. import copy cctv = ['1','2','3','4','5'] N,.. [백준] 1068번 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 자기자신으로부터 방문할 수 있는 노드를 graph의 배열에 넣어둔뒤, 루트노드로부터 자식 노드들을 방문해가면서 각각의 노드들의 자식노드가 0일경우 cnt값을 증가시켜 문제를 해결 하였습니다. 루트노드가 지워진 노드일경우는 트리 자체가 사라지기 때문에 0으로 예외사항을 추가 했습니다. N = int(input()) nodeInput = list(map(int ,input().split())) .. 이전 1 2 3 다음