[백준 JAVA] 4196 : 도미노

[백준 4196] 도미노 : https://www.acmicpc.net/problem/4196문제 조건 도미노가 한쪽 방향으로만 넘어지기에 단방향 간선으로 표현되지만, 실제로는 우리가 원하는 방향(왼쪽 또는 오른쪽)으로 도미노를 밀어 넘어뜨릴 수 있다. 즉, 한 도미노가 넘어진 방향에 따라 연쇄 반응을 일으키는 관계가 결정되는데, 이때 도미노를 그래프로 나타내면 간선이 기본적으로 한 방향(진출 간선)만 표시된다. 하지만 만약 어떤 도미노가 한쪽 방향에서는 연쇄 반응을 일으키지 못한다면, 그 도미노의 반대쪽(진입 간선) 방향으로도 연쇄 반응을 고려할 수 있어야 한다. 그래서 DFS를 진행할 때, 상황에 따라 진출 간선과 진입 간선을 서로 뒤바꿔서 탐색할 수 있다는 뜻이다. 이는 단순히 양방향 그래프가 되는..

2025.02.08