본문 바로가기
반응형

dfs10

프로그래머스 - 여행경로 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 풀이 조건을 보면 주어진 항공권은 모두 사용해야하며 가능 경로가 2개 이상일 때에는 알파벳 순서가 앞서는 경로를 return한다고 되어있다. 나는 DFS로 풀이할 것이기 때문에 visited 배열을 티켓에 대해 체크하는 용도로 사용했다. 우선, 알파벳 순서가 앞서는 경로를 먼저 확인하기 위해 tickets 배.. 2022. 2. 19.
프로그래머스 - 단어 변환 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 풀이 현재 단어에서 하나의 문자만 다른 단어를 찾아 해당 단어부터 다시 DFS를 거치는 방식으로 풀면 된다. 먼저, 두 단어가 한 가지의 문자만 다른지 찾는 함수를 구현해준다. bool isAbleToChange(string a, string b){ int cnt = 0; for(int i=0; i .. 2022. 2. 19.
프로그래머스 - 네트워크 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 풀이 n은 컴퓨터의 개수이고 최대 200개이다. 따라서 방문 여부 체크를 할 수 있는 visited 배열은 200번째 인덱스까지 선언해준다. 0번 컴퓨터부터 n번 컴퓨터까지 DFS를 거쳐 연결된 컴퓨터를 체크한다. DFS 함수 내부에는 다시 0부터 n까지 해당 노드와 연결되어 있는 노드들에 대해서 DFS를 거치는데, 문제의 조건 중에서 .. 2022. 2. 15.
프로그래머스 - 타겟 넘버 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 풀이 주어진 숫자를 더하고 빼서 target이 될 수 있는지 찾는 문제이다. numbers 배열의 크기가 크지 않으므로 DFS를 통해 모든 더하기, 빼기의 경우의 수를 체크해보면 된다. 소스 코드 #include using namespace std; int answer = 0; void DFS(vector numbers.. 2022. 2. 13.
반응형

티스토리툴바