문제https://www.acmicpc.net/problem/1103설명 전형적인 그래프 탐색 문제이지만, 사이클이 발생한 경우를 탐지해야 하므로 BFS 대신 DFS를 사용하는 것이 효율적이다. 그러나 단순히 DFS를 수행하며 동전이 움직일 수 있는 최대 횟수를 구하려고 하면 시간 초과가 발생하게 된다. 이미 방문한 지점인 경우, 추가적인 탐색을 진행하면 안 된다. 따라서 DP 배열을 추가로 선언해야 한다.코드더보기#include #include using namespace std;int ans = 0;bool cycleFlag = false;int n, m;int board[50][50];int visited[50][50];int cnt[50][50];int dx[4] = { -1,0,1,0 };int..

문제https://www.acmicpc.net/problem/2533설명DFS로 트리를 순회하며 가능한 얼리 어답터의 수를 구하는 문제이다. 최소 얼리 어답터의 수를 구하기 위해 DP를 사용한다. 먼저 노드 연결 관계를 vector 배열 nodes에 저장한다. DFS로 순회하며 DP 배열을 초기화한다. 사용할 DP 배열은 이차원 배열이다. dp[i][j]는 i번 째 노드가 얼리 어답터(j == 1) 또는 얼리 어답터가 아닐 때(j == 0) 가능한 최소 얼리 어답터의 수이다. 현재 참조하는 노드를 node, 자식 노드를 child라고 할 때 child의 DFS 순회를 마치고 node에 대한 DP배열을 초기화한다. node가 얼리 어답터가 아닐 때 자식 노드는 무조건 얼리 어답터여야 한다. 즉, dp[no..

문제https://www.acmicpc.net/problem/16724설명주어진 지도의 사이클의 개수를 찾는 문제이다. 각 노드에 대하여 DFS를 수행하여 사이클을 찾는다. DFS를 수행 후 리턴될 때 visited[i][j]을 -1로 설정한다. 이는 추후 DFS를 수행 시 이미 생성된 사이클의 노드에 접근하지 못하게 하는 역할을 한다. 범위 밖으로 나가는 입력은 주어지지 않으므로 잘못된 배열 인덱스를 참조하는 경우는 고려하지 않아도 된다.코드더보기#include #include #include using namespace std;vector board;int visited[1000][1000]; // 1: 방문, -1: 방문 완료int cnt = 0;void dfs(int x, int y) { visi..