Algorithm/BFS DFS17 [프로그래머스] 단어 변환 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43163# KEY 두 문자열의 요소가 1개만 다른지 확인하는 함수를 따로 작성했다. 처음에 방문 배열(visited)를 사용하지 않고 DFS로 풀이했는데, 테스트케이스 3번에서 시간초과가 발생했다. 결국 visited를 사용하여 방문했던 노드를 탐색하지 않는 과정을 추가 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include #incl.. 2023. 3. 14. [백준] 16953 A->B c++ 문제 링크 https://www.acmicpc.net/problem/16953 KEY 일반 구현으로도 문제풀이가 가능하나, DFS를 이용할 때 더 쉽게 접근할 수 있다. 2를 곱하거나, 뒤에 1을 붙이는 경우 총 2가지경우를 모두 탐색한다. 자료형을 주의깊게 보자.. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include #include #include using namespace std; long long A, B; int result = 999999999; void dfs(long long x, int cnt) { if (x > B) return; if (x == B.. 2023. 3. 13. [백준] 2644 촌수계산 c++ 문제 링크 https://www.acmicpc.net/problem/2644 KEY 두 노드 사이의 거리를 구하는 문제이므로, 하나의 노드를 기준으로 다른 노드에 도착할 때까지 거리를 증가시킨다. DFS풀이의 경우 재귀함수의 종료조건은 n번 순회를 끝낼 때로 정했다. 구하고자 하는 거리 배열을 0으로 초기화했기 때문에 방문하지 않은 노드의 경우 0이 된다. ◈ DFS풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #include #include #include #include using namespace std; const .. 2023. 3. 12. [백준] 1389 케빈 베이컨의 6단계 법칙 c++ 문제 링크 https://www.acmicpc.net/problem/1389 KEY N번까지의 노드를 하나씩 출발노드로 지정하면서 (노드, 이동거리)의 큐를 만들어 이동거리의 합을 구하면 된다. 테스트케이스에서 예를 들어보면 다음과 같다. 1번노드에서 출발했을 때 1번(1,0) -> 3번(3,1), 4번(4,1) -> 2번(2,2), 5번(5,2) 따라서 이동거리의 총 합은 0+1+1+2+2 = 6 이 과정을 1~N노드까지 반복수행 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53.. 2023. 3. 10. [백준] 2583 영역 구하기 c++ 문제 링크 https://www.acmicpc.net/problem/2583 KEY 입력형식을 적절하게 바꾸어서 색칠된 부분을 표현하는 것이 중요했다. 나같은 경우는 좌표형식을 배열인덱스로 갖고 오고자 x좌표와 y좌표를 뒤집었다.(모양은 뒤집어지지만 넓이는 같다) ex) 테스트케이스에서 예시를 들어보면, 좌표값 (4,0), (6 2)를 뒤집어 (0,4),(2,6)를 만들고, 이는 배열 arr[0][4]에서 arr[1][5]까지 색칠되었다고 표현할 수 있다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 .. 2023. 3. 2. [백준] 11725 트리의 부모 찾기 c++ 문제 링크 https://www.acmicpc.net/problem/11725 처음에는 DFS로 접근하지 않고 입력받을 때 조건에 따라 2차원 배열에 push_back하는 방법으로 풀었다. 2개의 테스트케이스를 통과했지만 제출하면 런타임오류(Out of Bounds)가 뜬다. 아무리봐도 배열 index에 문제가 없어보이는데.. 다시 찾아봐야겠다.. 오답 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include #include #include using namespace std; int n; vector .. 2023. 3. 2. 이전 1 2 3 다음
