• 티스토리 홈
  • 프로필사진
    유니얼
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
유니얼
  • 프로필사진
    유니얼
    • 분류 전체보기 (295)
      • Unity (17)
        • 게임 개발 (5)
      • Unreal (24)
        • 게임 개발 (20)
      • DirectX (36)
      • 코딩테스트 (91)
        • 프로그래머스 (25)
        • 백준 (66)
      • Google Workspace (1)
      • Programing (102)
        • C# (68)
        • C++ (24)
        • JavaScript (10)
      • 게임 서버 프로그래밍 (17)
      • Web (6)
        • 슈퍼코딩 (6)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
    등록된 댓글이 없습니다.
  • 최근 공지
    등록된 공지가 없습니다.
# Home
# 공지사항
#
# 태그
# 검색결과
# 방명록
  • [99클럽/코딩테스트 챌린지/C++] "YES or yes" 문제 풀이
    2024년 11월 07일
    • 유니얼
    • 작성자
    • 2024.11.07.:06
    728x90

    주어진 단방향 그래프에서 출발 정점(1번)에서 시작하여 특정 정점에 팬클럽이 있는 경우를 피할 수 없는지 여부를 확인하는 문제입니다. 출발 정점에서 가능한 모든 경로를 탐색하며, 팬클럽을 만나지 않고 종착점에 도달할 수 있는 경우 "yes"를, 그렇지 않다면 "Yes"를 출력합니다.

    문제 링크 :

    https://www.acmicpc.net/problem/25195

    접근법

    1, 그래프 초기화: 주어진 정점 수와 간선을 기반으로 단방향 그래프를 구성합니다. 또한 팬클럽이 있는 위치를 표시하기 위해 has_fanclub 배열을 초기화하여 팬클럽이 있는 정점은 2로 표시합니다.

     

    2, BFS 탐색: BFS를 사용하여 출발 정점(1번)에서 이동 가능한 모든 경로를 탐색합니다. 이때, 팬클럽이 있는 정점(2)으로 이동하는 경로는 무시합니다. 이렇게 함으로써 팬클럽이 없는 경로만을 탐색할 수 있습니다.

     

    3, 종착점 확인: BFS 탐색 후, 팬클럽을 만나지 않고 방문한 종착점이 있는지 확인합니다. 종착점 중 하나라도 팬클럽을 만나지 않고 도달한 경우가 있다면 "yes"를, 그렇지 않다면 모든 경로에서 팬클럽을 만나게 되는 것이므로 "Yes"를 출력합니다.

     

    코드 설명 : 

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    int main() {
        int N, M;
        cin >> N >> M;
    
        vector<vector<int>> graph(N + 1); // 정방향 그래프
        vector<int> has_fanclub(N + 1, false); // 팬클럽이 있는 정점을 표시
    
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
        }
    
        int S;
        cin >> S;
    
        for (int i = 0; i < S; i++) {
            int s;
            cin >> s;
            has_fanclub[s] = 2;
        }
    
        if(has_fanclub[1] == 2)
        {
            cout << "Yes" << endl;
            return 0;
        }
    
        // BFS 탐색을 시작하며, 방문 여부를 1로 표시합니다.
        queue<int> tour;
        tour.push(1);
        has_fanclub[1] = 1;
    
        while (!tour.empty()) {
            int node = tour.front();
            tour.pop();
    
            for (int next : graph[node]) {
                // 팬이 없는 경우에만 다음 정점으로 이동합니다.
                // => 다음 경로에 팬이 있는 경우에는 해당 경로는 필요 없으므로 무시합니다.
                if (has_fanclub[next] == 0) {
                    has_fanclub[next] = 1;
                    tour.push(next);
                }
            }
        }
        // 팬을 만나지 않고 도달한 종착점이 있는지 확인
        bool flag = false;
        for(int i = 1; i <= N; i++)
        {
            // 팬이 없는 경로만 탐색했을 때, 해당 정점을 방문했다면
            // 팬을 만나지 않는 경로가 존재합니다.
    	    if(graph[i].size() == 0 && has_fanclub[i] == 1)
    	    {
                flag = true;
    	    }
        }
        if (flag == true) {
            cout << "yes";
            return 0;
        }
        cout << "Yes";
    
        return 0;
    }

    배운 점

    1, BFS를 통한 조건에 따른 경로 탐색

    BFS를 통해 출발 정점에서 도달할 수 있는 모든 정점을 탐색하며, 팬클럽이 있는 경로는 무시하도록 설정함으로써 조건에 맞는 경로를 탐색하는 방법을 배웠습니다. 특정 조건을 가진 정점은 탐색하지 않는 방식으로 경로를 제한할 수 있음을 이해했습니다.

    2, 종착점 확인을 통한 최종 조건 판별

    모든 종착점에서 팬클럽을 만나지 않은 정점이 있는지 확인하여 경로의 조건을 판별할 수 있었습니다. BFS 탐색 후, 방문 여부와 종착점을 통해 경로 조건을 확인할 수 있다는 점을 다시 한번 깨달았습니다.

    결론

    이 문제를 통해 탐색 경로에 특정 조건이 있을 때 조건에 맞는 정점만 탐색하는 방법을 익혔습니다. 또한, 종착점에서 특정 조건을 확인하는 방식으로 최종 결과를 도출하는 접근이 적절함을 배웠습니다. 앞으로도 그래프 문제에서 조건에 맞는 경로를 효율적으로 탐색하고 조건을 판별할 수 있을 것 같습니다.

    반응형
    다음글
    다음 글이 없습니다.
    이전글
    이전 글이 없습니다.
    댓글
조회된 결과가 없습니다.
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
목차
표시할 목차가 없습니다.
    • 안녕하세요
    • 감사해요
    • 잘있어요

    티스토리툴바