Approach DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성을 없애기 위해서 큐에 넣자마자 방문처리를 해줘야 한다. 이 부분때문에 처음에 메모리초과를 받았다. Code #include #define fastio ios_base::sync_with_stdio(0); using namespace std; typedef pair pii; char r[100][100]; int visited[100][100]; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int main(void){ fasti..

Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int m, n; int edge[51][51]; int visited[51][51]; vector node; void dfs(int x_val, int y_val){ visited[x_val][y..

앞의 술레잡기 문제와 비슷하게 가중치가 동일한 문제의 최단거리는 BFS로 처리할 수 있다. (만약 그렇지 않은 경우는 Dijikstra로 처리해야 한다.) 이 문제의 경우는 숫자가 겹칠 일이 없으므로 딱히 visited를 처리해서 진행해주지 않아도 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; typedef long long ll; typedef pair pll; int main(void){ fastio; queue data_store; int a, b; cin >> a >> b; data_store.push(make_pair(a, 0)); while(data_sto..

이 문제와 숨바꼭질1과의 차이점은 중복되는 것의 유무를 어떻게 처리할 것인가에 대한 유무이다. 앞 문제에서는 queue에 넣을 때 visited를 처리하였다. 왜냐하면 어차피 동일한 시간이 걸리는 것이 존재해도 어차피 시간이 같으므로 지워도 무방하기 때문이다. 다만, 이 문제의 경우 최소일 때 몇 가지 인지 체크해야하는 문제이므로 동일한 시간이 걸리는 경우에는 모두 다 살려주어야 한다. 즉, visited처리하는 순간이 그 이후 타이밍이어야 한다. 즉, pop시키는 순간에 visited처리해 주면 1번과 근본적으로 동일하게 접근할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespa..

처음에 단순히 3가지 케이스를 큐에다가 넣고 처리하려고 하였다. 하지만, 문제점이 데이터가 너무 많다.. 최악의 경우 3^100000인데 너무너무 크다. 이러한 문제점이 나타나는 근본적인 이유는 중복이 되기 때문이다. 잘 생각해보면 나중에 중복되는 숫자는 이전에 나온 것 보다 무조건 시간이 더 느릴 수 밖에 없으므로 기존에 방문한 것을 제외하고 처리해주면 된다. 일종의 DP 아이디어를 활용한다고 생각해도 무방하다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; typedef pair pii; int main(void){ fastio; int N, K; cin >> N >> ..

대략적으로 그래프를 타고 넘어가면서 전파하는 양상이라는 것을 문제를 읽어보면 쉽게 판단할 수 있다. 처음에 생각한 방법은 DFS인데, 중간에 문제점이 있다는 것을 파악하고 포기하였다. 예를들어 DFS를 타고 넘어가면서 8분 정도에 특정 노드에 전파할 때 절반을 넘었다고 가정해보자. 단순하게 8분을 전파시점으로 생각하기 쉬우나, 이렇게 단순하게 접근하면 안된다. 예를 들어 다른 간선에서는 4분에 해당 노드에 접근을 시도했을 수도 있기 때문이다. 즉, 해당 간선을 기준으로 만족한다고 하여 그것이 가장 짧은 시간임을 보장할 수가 없게 된다. 따라서 이 부분에서 BFS를 강구한 것이다. 즉, 같은 시간에 전파되는 것들을 모두 다 처리하고 넘어가야 해당 노드에 전파되는 시점의 대소비교가 가능해진다. 귀찮아서 BF..

DFS, BFS를 처음 배운 입장에서는 좀 까다로운 문제였다. 이 문제를 보고 처음 접근한 방식은, DFS이다. 실제로 구현 방법이 아직까지는 DFS가 재귀로 짜기 쉽기도하고, 두 가지 방법의 근본적인 차이에 대해서 잘 이해하지 못했기 때문이다. 일단, 이 문제를 DFS로 바라보면 안되는 이유에 대해서 정리하자면, 1. 너무 불필요하게 하나의 케이스를 기준으로 건물 양 끝을 오가게 된다. 정확하게 이 문제를 이해해보면, 올라가는 케이스와 내려가는 케이스를 기준으로 해당하는 칸을 갈 수 있는지를 체크하는 것이 중요하다. 그런데, 만약에 해당하는 칸을 가면 참 좋겠지만 가지 못한다면 잘못하면 무한루프에 빠질 가능성이 존재한다. 위 문제에서 최저값이 1층 최고값이 입력에서 제한되어 있는 상황이므로 계속해서 계..