[BOJ/20955] 민서의 응급 수술, c++

2021. 3. 8. 01:50·DEV/PS

www.acmicpc.net/problem/20955

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

한줄 후기: 수술은 의사에게..

 

그래프 문제처럼 보인다.

처음의 mst 관련인가 하고 생각했는데 문제를 읽어보니 대충 연결 요소의 개수를 구해주면되는 거 아닌가? 하고 바로 코드를 작성했다.

틀렸다!

다시 문제를 읽어보니 민서가 할 수 있는 연산이 2개이다. 난 이중 뉴런끼리 연결을 끊는 연산을 간과했다.

 

뉴런끼리 연결을 끊어야만 하는 경우가 언제일까? 

사이클이다! 

민서는 트리를 만들고 싶어하는 것이니 사이클은 필히 지워주어야 한다. 

따라서 연결요소의 개수 -1 + 사이클 개수가 최소 연산 횟수가 된다.

(사이클에서 간선 하나만 지우면 되니까)

사이클 detect를 어찌할까 하다 union-find를 쓰려했는데 그냥 dfs 구현했던거에 코드를 추가해서 사이클을 감지했다.

 

//AC
//BOJ 20955 민서의 응급 수술
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[101010];
bool visit[101010];
bool cycle[101010];
int N, M, cnt = 0;
void dfs(int s, int prev){
	visit[s] = true;
	for(int tmp : v[s]){
		if(!visit[tmp]){
			dfs(tmp, s);
		}
		else if(!cycle[tmp] && tmp != prev){
			cnt += 1;
		}
	}
	cycle[s] = true;
}
int main(){
	int ans = 0;
	scanf("%d %d", &N, &M);
	for(int i=0; i<M; i++){
		int U, V;
		scanf("%d %d", &U, &V);
		v[U].push_back(V);
		v[V].push_back(U);
	}
	for(int i=1; i<=N; i++){
		if(!visit[i]){
			dfs(i, 0);
			ans += 1;
		}
	}
	printf("%d", ans-1+cnt);
	return 0;
}

 

 

저작자표시 비영리 변경금지 (새창열림)

'DEV > PS' 카테고리의 다른 글

[BOJ/20924] 트리의 기둥과 가지, c++  (0) 2021.03.29
[BOJ/9466] 텀 프로젝트, c++  (0) 2021.03.16
[BOJ/20956] 아이스크림 도둑 지호, c++  (0) 2021.03.08
2021 SUAPC winter 주저리..  (0) 2021.03.04
[BOJ/2912] 백설공주와 난쟁이, c++  (0) 2021.02.19
'DEV/PS' 카테고리의 다른 글
  • [BOJ/20924] 트리의 기둥과 가지, c++
  • [BOJ/9466] 텀 프로젝트, c++
  • [BOJ/20956] 아이스크림 도둑 지호, c++
  • 2021 SUAPC winter 주저리..
jobchae
jobchae
말하는 감자지만, 코드를 끄적이는 Node.js 백엔드 개발자입니다.
  • jobchae
    JOBCHAE
    jobchae
  • 전체
    오늘
    어제
    • 🚀 JOBCHAE (177)
      • DEV (146)
        • PS (108)
        • Node.js (12)
        • React (3)
        • docker (1)
        • 잡다한 개발 일지 (20)
        • injection (1)
        • CI CD (0)
        • JS, TS (1)
      • 축구 (0)
      • 일상 (19)
      • 영화 (3)
      • 음악 (8)
  • 블로그 메뉴

    • 💻 Github
    • 🙋🏻 Linkedin
    • 📖 방명록
  • 링크

    • PS Github
  • 공지사항

  • 인기 글

  • 태그

    슬랙
    리액트
    DFS
    앱잼
    이분탐색
    BFS
    slack
    솝트
    PS
    Nest.js
    슬랙봇
    typescript
    알고리즘
    node.js
    boj
    일상
    SOPT
    우선순위큐
    react
    mongoDB
    Express
    위상정렬
    Nest
    백준
    회고
    DP
    aws
    nodejs
    렛츠락페스티벌
    GitHub
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
jobchae
[BOJ/20955] 민서의 응급 수술, c++
상단으로

티스토리툴바