dfs

[프로그래머스 Lv.2] 괄호 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이DFS와 구현이 섞인 문제로 볼 수 있다. 흔히 볼 수 있는 DFS 문제와 다르긴 하나, 재귀를 사용해 한 문장 p의 끝까지 들어가며 특정 로직을 적용하기에 DFS 문제라고 생각한다.구현 부분은 어려운 알고리즘을 사용하는 게 아니다 보니, 문제에 주어진 대로 그저 한 단계씩 구현하면 된다. 한 단계씩 구현해 나가고, 재귀적으로 다시 실행해야 하는 부분은 DFS를 통해 진행하면 비교적 쉽게 풀 수 있다.  처음에는 p의 길이가 10..

[프로그래머스 Lv.3] 여행경로 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이DFS를 활용한 문제이다. dictionary를 활용하여 전체 티켓들을 사용해 마치 graph와 같은 구조를 완성하고, 이를 DFS로 순회하면 된다. DFS로 순회하며, 더 이상 이동할 수 없는 경우가 되면 그 때 위치하는 공항을 answer 배열에 저장한다.다만 주의해야할 점이 있는데, 가능한 경로가 2개 이상일 땐 알파벳 경로가 앞서는 경우를 반환하라고 했기 때문에 그래프를 완성할 때 정렬이 필요하다는 점을 고려하며 구현해야 ..

[프로그래머스 Lv.2] 타겟 넘버 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이재귀함수를 사용한 DFS를 이용한 풀이이다.재귀함수의 인자로는 숫자들을 사용하여 더하거나 빼기를 진행한 현재까지의 누적값이고, 다른 하나는 현재까지 더하기 또는 빼기에 사용한 숫자의 수이다.초기값은 누적값은 0, 사용한 숫자의 수는 0으로 하였다.종료 조건은 당연하게도 모든 숫자가 사용되었을 때, 즉 numbers 배열의 길이와 사용한 숫자의 수가 같을 때이다.또한, 종료할 때 만약 문제에서의 조건인 누적합이 타겟 넘버와 같은 경..

[프로그래머스 Lv.3] 네트워크 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. from collections import dequedef solution(n, computers): answer = 0 ..

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다. 코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다. "(", 열린 괄호로 시작하여 나올 수 있는 괄호 조합들을 하나씩 탐색하는 것을 DFS 알고리즘을 사용하여 풀이하였다. 열린 괄호의 수를 open, 닫힌 괄호의 수를 close라고 하고, 아래와 같은 종료 조건들을 ..

(JAVA) 양과 늑대

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 class Solution { int[] gInfo; // DFS에서 사용할 노드의 정보 int[][] gEdges; // DFS에서 사용할 간선의 정보 int maxValue = 0; public int solution(int[] info, int[][] edges) { gInfo = info; gEdges = edges; boolean[] isVisited = new bool..

(C++) 백준 1260번 - DFS와 BFS

문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 그래프에서의 DFS와 BFS를 구현하는 문제이다. DFS는 Stack을, BFS는 Queue를 사용해서 풀력 형식에 맞게 그래프의 정점을 하나씩 순회하도록 구현하면 된다. #include #include #include #include using namespace std; vector gp[1002]; int visited[1002]; qu..

(C++) 백준 1926번 - 그림

문제 링크 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS를 사용하여 풀이하면 되는 문제이다. 그림의 시작점을 찾기 위해 전체적으로 이중 for문으로 스캔하면서 아직 방문하지 않은 시작점을 찾는다. 그 후 BFS를 사용하여 인접 칸들을 순회하면서 그림의 크기를 알아내었다. #include #include #include #define X first #define Y second using namespace std; int dx[4] ..