전체 글 (84) 썸네일형 리스트형 백준 4196 도미노 www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 본 블로그 SCC관련 포스팅에서 num값이 크면 가장 멀리 있는 정점까지 도달할 수 있는 가능성이 있다고 하였다. 약간 위상정렬에서 순서가 가장 앞서는 정점에서 시작해야 모든 정점을 돌 수 있는 것처럼, SCC를 찾을 때 첫 번째 DFS에서 매겨둔 num값 중 가장 큰 값에서 시작하면 가장 멀리 갈 가능성이 있다. (절대 항상 그런건 아니다. 주의!) 이 도미노 문제는 어떠한 블록을 넘어뜨리면 가장 멀리 가는 경우 (또는 가장.. 강한 연결 요소 - Strongly Connected Component (SCC) 개인적으로 그래프, 트리 등을 좋아하는 편이다. 이 알고리즘도 그래서 매우 재미있게 익힐 수 있었다. 강한 연결 요소는 DG (Directed Graph, 단방향 그래프)에서 사이클을 찾는 방법이다. 그리고 그 사이클은 포함할 수 있는 모든 정점을 최대한으로 포함시켜준다. - 사이클을 이룰 수 있는 최대 크기 파악 가능 (하나의 사이클을 이루는 최대한 많은 정점 모두 포함) - 사이클의 총 개수 - 사이클을 이루는 정점 번호 - 사이클을 하나의 정점으로 치환 후 위상정렬과의 연계 등등 다양한 기능을 수행한다. 본 포스팅에서는 코사라주 알고리즘으로 SCC를 찾아보겠다. 기본적인 방식은 DFS를 통해 하나의 정점에서 도달할 수 있는 최대한 먼 곳에서 가까운 순으로 번호를 달아주고, 역방향 그래프 상에서 다시.. 백준 6543 그래프의 싱크 www.acmicpc.net/problem/6543 6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net 이 문제는 SCC를 활용할 수 있는 문제이며, 본 블로그 내의 SCC 관련 포스팅을 꼭 같이 참조하기 바란다. 이 문제는 SCC를 찾기만 하는 게 아니다. SCC를 이루는 요소에서 다른 정점 어디라도 갈 수 있는데, 돌아오지 못한다면 답이 아니게 된다. 위의 그림은 이전 SCC포스팅에서 사용한 그림이다. 위와 같은 그래프에서는 1-2-3이 원래 SCC를 이루지만, 3에서 4와 5도 갈 수 있고, 4와 5에서는 1.. 백준 17142 연구소 3 (삼성 기출) www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제도 삼성 문제의 유명한 연구소 시리즈 중 하나이다. 이런 격자구조가 나오면 항상 BFS/DFS/DP 등을 생각하게 되는데, 이 문제도 BFS로 풀었다. 다만 조합을 끼얹어야 한다. 바이러스를 놓을 수 있는 위치들은 맵 상에 표시되어있고, 그 중에서 가장 빠른 확산을 일으킬 수 있는 최적의 M개를 골라야 하는데, 이 M개 선택에 있어 순서는 중요하지 않다. 그래서 순열이 아니라 조합이 된다. 조합에 대해서는 N과 .. 백준 17144 미세먼지 안녕! (삼성 기출) www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 전형적인 구현 및 시뮬레이션 문제이다. 구현 및 시뮬레이션 문제를 풀 때는, (사실 모든 문제가 마찬가지지만) 주어진 조건을 잘 파악하여야 한다. 그리고 중복되는 부분이나 자주 호출되는 부분이 있는지 확인해보고, 예외 상황 등을 파악한다. 그리고 모듈화 (함수나 클래스 등으로 코드의 일정 단위를 묶어주는 등)를 잘해주어야 한다. 보통 이런 격자구조가 나오면 기본적으로 좌, 우, 위, 아래 탐색을 해주는 BFS.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 17 다음
