본문 바로가기

Algorithm/DFS

 (45)
(C++) - LeetCode (easy) 104. Maximum Depth of Binary Tree https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com dfs로 해결한 문제였습니다. 📕 풀이방법 📔 풀이과정 terminal node에서 0을 반환하고 더 깊은 depth로부터 1씩 더해 가장 큰 depth를 반환하는 dfs함수를 구현합니다. 📔 정답출력 dfs함수의 결과를 반환합니다. 📕 Code 📔 C++..
(C++) - 백준(BOJ) 16929 : Two dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net cycle을 판별하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 행 n, 열 m, 정답 ans, 시작점 sr,sc, 방문여부를 확인할 ck, 방향 dr,dc, board 를 선언하고 입력받습니다. 📔 풀이과정 2중 for loop를 수행하면서 같은 문자끼리 dfs로 방문해줍니다. 1. 인접칸을 방문하면서 dfs함수를 호출해줍니다. 호출당 길이가 1씩 증가합니다. 2. 최소 사이클의 길..
(C++) - 백준(BOJ) 17070 : 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 모든 경우를 backtracking으로 탐색해 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 집 한변의 길이 n, 집의 구조를 입력받을 2차원 배열 house, n행 n열에 도착하는 경우의 수를 출력할 cnt를 선언합니다. 2. 길이 n행 또는 n열을 초과하는 모두 벽으로 생각해 house의 값들을 모두 1로 초기화해줍니다. 3. 1행 1열 ~ n행 n열까지 ..
(C++) - 백준(BOJ) 1595번 : 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net dfs로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접 도시로 가는 경로가 1개인 연결그래프는 트리입니다. 이 트리구조를 저장하기 위해 struct Edge를 만들어 양방향그래프를 저장합니다. 📔 풀이과정 단순히 건너간 간선이 최대라고 거리까지 최대가 되지는 않습니다. 또한 어떤 도시에서 다른 도시로 갈때는 말단 노드(도시)를 경유지로 가면 안됩니다. 출발도시에서 말단 노드(도시)로 가는 ..
(C++) - 프로그래머스(위클리 챌린지) : 5주차 https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 조합 + 정렬문제였습니다. 📕 풀이방법 📔 입력 및 초기화 나올 수 있는 모든 형태의 문자열을 저장하기 위한 vector변수 dictionary를 선언합니다. 📔 풀이과정 1. 나올 수 있는 모든 문자열을 dictionary에 push해줍니다. 2. 자리마다 확인하며 사전상 앞에 오는 문자 순으로, 자리수에 대한 오름..
(C++) - 백준(BOJ) 17478번 : 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀함수를 이해하기 좋은 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n을 입력받습니다. 📔 풀이과정 1. 기저 조건 세우기 : depth == n이면 출력 후 종료합니다. 2. 재귀 수행 : dfs함수 호출 전 본문 출력하고, dfs함수 호출 합니다. dfs함수가 종료되면 "라고 답변하였지."를 출력합니다. 📕 Code //재귀함수가 뭔가요? #include using namespace st..
(C++) - 백준(BOJ) 20166번 : 문자열 지옥에 빠진 호석 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net dfs문제였습니다. 📕 풀이방법 k를 입력받을 때마다 dfs를 수행한다면 tle입니다. 따라서 전처리로 dfs 후 k를 입력받아야 합니다. 📔 입력 및 초기화 n,m,k 입력 후 문자열 배열 board에 적절히 입력받습니다. 📔 풀이과정 1. n행 m열을 모두 돌며 board[i][j]를 시작점으로 dfs를 수행해 줍니다. 2. dfs 수행 시 만든 문자열을 모두 map에 넣어줍니다. 해당 문자열의 value를 1씩 증가시킴으로써 경우의 수를 구할 수 있습니다. 📔 정답출력 k만큼..
(C++) - 백준(BOJ) 5568번 : 카드놓기 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 순열문제였습니다. 풀이방법 1. 자기자신을 뽑지 않으면서 순서 상관있도록 뽑으면됩니다. 2. 카드를 뽑았으면 카드들을 나열한 뒤 set에 넣어줍니다. 3. set의 size를 출력합니다. Code #include using namespace std; int n,k; vector card; set cardSet; vector tmp; int ck[11]; void dfs(int depth){ if(depth == k){ string c; for(auto t : tmp) c += t; cardS..

티스토리툴바