• 티스토리 홈
  • 프로필사진
    학페
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
학페
  • 프로필사진
    학페
    • 분류 전체보기 (38)
      • Baekjoon Online Judge (30)
        • C++ (30)
      • Data structure & Algorithm (7)
      • Java (1)
        • Java Spring (0)
        • Spring 공부하며 정리하는 개념들 (1)
      • Open API (0)
      • 일상 이야기 (0)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
      등록된 댓글이 없습니다.
    • 최근 공지
        등록된 공지가 없습니다.
      # Home
      # 공지사항
      #
      # 태그
      # 검색결과
      # 방명록
      • BOJ - 바이러스 (2606번)
        2022년 09월 03일
        • 학페
        • 작성자
        • 2022.09.03.오후07:36

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

         

        2606번: 바이러스

        첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

        www.acmicpc.net

        DFS를 사용하는 문제였습니다.

        DFS와 BFS 정리하는 겸 해결해봤습니다.

         

        재귀함수를 사용한 기본적인 틀은 동일합니다만, 하나 추가적으로 생각해줘야 할 부분이 있습니다.

         

        이 문제는 컴퓨터가 양방향으로 연결되어 있다고 보고 해결해야 하는데요, 이 부분만 코드로 추가해주면 어렵지 않게 해결할 수 있습니다.

         

        #include <iostream>
        #include <string>
        #include <vector>
        #include <cmath>
        #include <algorithm>
        #include <utility>
        #include <stack>
        #include <queue>
        #include <deque>
        #include <utility>
        
        #define MIN 0
        #define MAX 10000000
        
        using namespace std;
        typedef unsigned long long int ll;
        
        vector<int> graph[101];
        bool infected[101] = { false, };
        
        void dfs(int x);
        int cnt = 0;
        int main() {
        
        	ios::sync_with_stdio(false);
        	cin.tie(NULL);
        	cout.tie(NULL);
        
        	//DFS 사용
        
        	int com; // 컴퓨터 수
        	int pair; // 연결된 컴퓨터 쌍의 수
        	cin >> com >> pair;
        	for (int i = 1; i <= pair; i++)
        	{
        		int a, b;
        		cin >> a >> b;
        		graph[a].push_back(b);
        		graph[b].push_back(a);
        	}
        	infected[1] = true;
        	dfs(1);
        	cout << cnt << '\n';
        }
        
        void dfs(int x) 
        {
        	infected[x] = true; // 감염됨
        	for (int i = 0; i < graph[x].size(); i++) // x번 컴퓨터와 연결된 수 만큼 반복
        	{
        		int temp = graph[x][i]; // x번 컴퓨터와 연결된 컴퓨터의 번호가 들어감
        		if (!infected[temp]) {// x번 컴퓨터와 연결되었는데, 감염 표시가 안되었다면
        			dfs(temp);
        			cnt++;
        		}
        		// 감염됐음을 표시하고, graph[temp]와 연결된 
        		//또 다른 그래프가 있는지 확인하기 위해 재귀
        	}
        }

        graph[a].push_back(b);
        graph[b].push_back(a);

         

        이 부분이 양방향을 구현하는 부분이었습니다.

         

        다음은 BFS를 풀어봐야겠네요. 감사합니다.

        'Baekjoon Online Judge > C++' 카테고리의 다른 글

        BOJ - 토마토 (7576번)  (0) 2022.09.08
        BOJ - 미로 탐색 (2178번)  (0) 2022.09.04
        BOJ - 5의 수난 (23037번) C++  (0) 2022.07.13
        BOJ - 중복된 숫자 (15719번) C++  (0) 2022.07.11
        BOJ - 연속합 (1912번) C++  (0) 2022.06.28
        다음글
        다음 글이 없습니다.
        이전글
        이전 글이 없습니다.
        댓글
      조회된 결과가 없습니다.
      스킨 업데이트 안내
      현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
      ("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
      목차
      표시할 목차가 없습니다.
        • 안녕하세요
        • 감사해요
        • 잘있어요

        티스토리툴바

        개인정보

        • 티스토리 홈
        • 포럼
        • 로그인

        단축키

        내 블로그

        내 블로그 - 관리자 홈 전환
        Q
        Q
        새 글 쓰기
        W
        W

        블로그 게시글

        글 수정 (권한 있는 경우)
        E
        E
        댓글 영역으로 이동
        C
        C

        모든 영역

        이 페이지의 URL 복사
        S
        S
        맨 위로 이동
        T
        T
        티스토리 홈 이동
        H
        H
        단축키 안내
        Shift + /
        ⇧ + /

        * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.