본문 바로가기
반응형

DFS6

[백준 13023] ABCDE 문제출처 : https://www.acmicpc.net/problem/13023 A → B → C → D → E 의 관계가 성립하는 그래프가 있는지 확인하는 문제 입니다.깊이 우선 탐색을 이용하여 4단계까지 깊이가 생성된다면 1을 출력하고, 생성되지 않는다면 0을 출력하면 됩니다.문제 이해하기아래와 같은 친구 관계가 있습니다.1번에서부터 친구 관계를 찾아보면 4단계의 깊이를 내려갈 수 없습니다. 2번에서 시작해도 마찬가지로 4단계의 깊이로 내려갈 수 없습니다. 4번이나 5번에서 시작해야만 4단계의 깊이로 내려갈 수 있습니다. 따라서 이 문제는 모든 친구를 A로 가정하고 다 확인해봐야 합니다.코드작성함정이 없고, 이해하기 쉽기 때문에 바로 코드를 작성하겠습니다.입력 받기mii = lambda : map(i.. 2024. 4. 27.
[백준 30090] 백신 개발 문제 출처 : https://www.acmicpc.net/problem/30090 30090번: 백신 개발 평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 $N$개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구 www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 B번, 고등부 A번 문제 입니다. 겹치는 문자열을 이어 붙여 가장 짧은 문자열을 만드는 문제 입니다. 예제를 확인해보면 3개의 입력이 주어집니다. RUST, VIRUS, STAND 입니다. 이 3개의 문자를 겹치는 부분을 하나로 만들어 잘 이어주면 VIRUSTAND 라는 문자열이 가장 짧은 문자열이 되고 이 문자열의 길이인 9를 출력하는 .. 2024. 3. 13.
[백준 24955] 숫자 이어 붙이기 문제 출처 : https://www.acmicpc.net/problem/24955 24955번: 숫자 이어 붙이기 철수는 수를 이어 붙이는 놀이를 좋아한다. 1과 2를 이어 붙이면 12가 되고, 17과 13을 이어 붙이면 1713이 된다. 100과 1000을 이어 붙이면 1001000이 된다. 1과 2를 이어 붙이되, 순서를 반대로 해서 2와 www.acmicpc.net 문제 이해하기 방문한 순서대로 숫자들을 이어 붙여서 출력하는 문제 입니다. 사실 이 문제는 LCA 항목에 있어서 LCA를 연습하려고 풀어본 문제인데 단순한 DFS로 해결되는 문제였습니다. 다만 이 문제에서 신경 쓸 부분은 두가지 입니다. 숫자들 더해주는 것이 아니라 이어 붙이는 것입니다. 답을 숫자가 아닌 문자열로 관리해야 합니다. 숫자.. 2023. 11. 10.
[백준 28219] 2023 정올 1차 주유소 문제 출처 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇 www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 1차 중등부 3번, 고등부 2번 문제 입니다. 문제 이해하기 N개의 마을이 있는데 도로가 N - 1개가 있습니다. 정점의 갯수보다 간선의 갯수가 1개 적다면 트리 모형이 아닌가 고민해봐야 합니다. 여기에 임의의 두 마을에 대해 두 마을을 잇는 경로가 정확히 하나 존재한다고 합니다. 이 말은 트리 형태의 마을이.. 2023. 8. 23.
[백준 25402] 2022 정올 트리와 쿼리 2022년도 정보올림피아드 2차 데회에서 초등부, 중등부, 고등부 모두 나왔던 문제입니다. 그럼 같이 풀어보도록 하겠습니다. 문제의 예제를 살펴 보겠습니다. 아래와 같이 연결 되어 있는데 S = {1, 2, 3, 4, 5, 6} 입니다. 7만 연결이 안되어 있는 상태 입니다. 이것을 아래와 같이 표현할 수 있습니다. 연결되어 있는 노드들을 확인해보면 다음과 같습니다. (1 - 2), (1 - 3), (1 -5), (2 - 3), (2 - 5), (3 - 5), (4 - 6) 이렇게 7개가 연결 되어있고, 연결강도가 7임을 확인할 수 있습니다. 즉 각 노드들이 연결 되어 있는 노드들의 갯수를 확인하는 것이 이 문제 입니다. 모두 구해보기 가장 쉽게 생각하면 S에 포함된 노드들이 각각 연결되어 있는지 확인하.. 2023. 8. 18.
[백준 22344] 2021 정올 그래프 균형 맞추기 문제 출처 : https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 이 문제는 2021년 정보올림피아드 2차 초등부, 고등부 문제 입니다. 초등부 문제이지만 고등부에서도 출제된 문제인 만큼 쉽지 않은 문제 입니다. 문제 자체를 이해하는건 어렵지 않습니다. 간선의 가중치가 있고, 간선과 이어진 두 정점의 합이 간선의 가중치가 되면 됩니다. 예제 입력을 보면서 이해해 보겠습니다. 정점 1, 2, 3을 값과의 혼란을 피하기 위해 A, B, .. 2023. 8. 16.
반응형

티스토리툴바