dfs

문제https://leetcode.com/problems/combination-sum-iv/description/입력1 결과ans: Int = nums를 이용해 target을 만들 수 있는 중복조합의 수해석dfs와 memorization을 섞은 문제로 해석 된다.target을 nums에 있는 수 만큼 내리는 top-down 방식으로 해결target이 음수로 가면 가능성이 없으므로 0target이 0이면 1을 리턴 코드class Solution { func combinationSum4(_ nums: [Int], _ target: Int) -> Int { var cache: [Int] = [Int](repeating: -1, count: target+1) cache[0] = 0..

문제https://www.acmicpc.net/problem/11724 입력n: Int = 정점의 개수m: Int = 간선의 개수u: 간선의 정점1v: 간선의 점점21 결과ans: Int = 그래프에 존재하는 연결 컴포넌트 개수해석제공된 간선 정보를 이용해서 인접 행렬을 채운다.이후 dfs를 통해 방문여부를 갱신하여 중복하여 방문하는 문제를 해결한다.코드import Foundationlet nm = readLine()!.split{$0 == " "}.map{Int($0)!}let (n, m) = (nm[0], nm[1])var adj: [[Int]] = [[Int]](repeating: [], count: n+1)for _ in 0..

문제https://www.acmicpc.net/problem/2667입력n = 지도의 크기 (가로 세로 크기)board: [[Character]] = [] , "0"과 "1"로 구성됨 board[i] = "0" = 집이 없는 곳board[i] = "1" = 집이 있는 곳5결과ans: Int = 단지 수 단진 내 집의 수를 오름차순으로 정렬 후 한줄 씩 출력해석2중 반복문을 돌며 집이 존재하고, 아직 방문한 적이 없다면 새로운 단지 이 때 dfs로 들어가면서 연결된 모든 집을 하나의 단지로 인식하고 방문하며 count하자. 코드import Foundationlet n = Int(readLine()!)!var board: [[Character]] = []for _ in 0.. Int { visited[..

문제https://www.acmicpc.net/problem/1450입력n: Int = 물건의 개수c: Int = 가방의 용량arr: [Int] = 물건의 무게들1 결과ans: Int = 가방에 넣는 방법의 수해석n이 크지 않아 조합으로 도전하려 했지만  ({{30}C_1} ~ {{30}C_{30}}) 까지 구한다고 하면 너무 많은 시간이 걸릴 것같아 실패했다. 여기서 비슷하게 느꼇던 문제가 생각났는데 바로 아래 문제다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제는 두 플레이어가 주사위들을 나눠가진 후 그 주사위 눈들의 합을 합쳐 승/무/패를 계..

문제https://www.acmicpc.net/problem/1520 입력n, m = 지도의 행 , 열 길이 arr: [[Int]] = 각 지점의 높이결과ans: Int = 이동 가능한 총 경로 수해석내리막길인지 판별한후 dfs를 통해 목적지에 도달 후 return을 통해 카운팅을 해주자.  코드import Foundationlet nm = readLine()!.components(separatedBy: " ").map{Int($0)!}let (n,m) = (nm[0], nm[1])var arr: [[Int]] = []for _ in 0.. Int { if x == n-1 && y == m-1 { cache[x][y] = 1 return 1 } if..

문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr입력 maps:[String] = 지도 문자열 maps[i] - "X" = 바다 - 숫자 = 무인도에 머물 수 있는 수결과ans: [Int] = 각 섬마다 최대 머물 수 있는 일 수 , 하나 없으면 [-1]해석X가 아니면 섬이므로 일단 들어가서 연결되어있는 모든 섬을 방문하여 숫자를 더한 다음 결과 배열에 담는다.방문했는지 여부를 알아야하니 visited 배열필요 코드import Foundationextension String { subscript(_ index: Int) -> String { ..