본문 바로가기

강한결합요소

[BOJ] 백준 [4013] ATM JAVA
알고리즘,PS/백준 2021. 11. 23. [BOJ] 백준 [4013] ATM JAVA https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net [문제] [풀이] 어우 .. 어질어질하다.. SCC 활용 DP 문제이긴 한데 , 처음에 SCC 집단들을 구해서 indegree가 0인거부터 진행했는데 왜 안되지..? 했다가 나중에 알고보니 start 지점이 정해져있다는 걸 뒤늦게 알았고 한참을 헤맸다 .. 접근방법 1. SCC집단을 구할 것. 2. SCC집단마다 번호를 매기고 , 이 자체를 하나의 Node로 취급하여 또 다른 tot..
[BOJ] 백준 [4196] 도미노 JAVA
알고리즘,PS/백준 2021. 11. 23. [BOJ] 백준 [4196] 도미노 JAVA https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net [문제] [풀이] x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다. 즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다. 그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은 어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다. 그래서 SCC (강한 결..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바