시간 문제, 분과 초

https://www.acmicpc.net/problem/2852

분과 초를 다루는 문제가 나올 경우 하나의 단위로 통일하여 계산하는 것이 좋다!

예를 들어 1분 20초와 3분 10초 간의 차이를 구하고자 한다면 이를 나누어 계산하는 것은
분과 초에 대해 따로 변수를 만들고 각각 60에 대한 제한이 생겨 계산이 힘들게 된다.

따라서 1분 20초는 80초로 3분 10초는 190 초로 바꾼 후 계산하면 110초의 차이가 있고
이를 다시 분과 초로 바꾸기만 하면 되는 것이다.

(위의 과정 없이 하나하나 구현하면 정말 길어진다... 정말....)
https://www.acmicpc.net/source/65505156
(장장 3000줄이나 된다...)

또한 시간을 따로 정수형으로 받지 않고 문자열로 받아 처리하면 슬라이싱으로 처리하면
입력 형태에 따라 바꿔줄 필요 없이 편하게 구현할 수 있다.

// MM:SS 형태로 출력
string print(int a)
{
    string d = "00" + to_string(a / 60);
    string e = "00" + to_string(a % 60);

    return d.substr(d.size() - 2, 2) + ":" + e.substr(e.size() - 2, 2);
}

// MM:SS 를 Sec 로 변환
int changeToInt(string a)
{
    return stoi(a.substr(0, 2)) * 60 + stoi(a.substr(3, 2));
}

// MM:SS - MM:SS 를 Sec - Sec 로 계산
int CalTime(string a, string b)
{
    return changeToInt(a) - changeToInt(b);
}

---

중복 방문

https://www.acmicpc.net/problem/2636

주어진 배열에서 1로 둘러쌓여진 영역의 경계를 구하는 문제로
1을 생각하지 말고 처음 한번 (0, 0) 에서 시작하는 dfs 를 만든 뒤

1이 나올 경우 해당 위치를 기억하여 해당 배열의 위치를 0으로 만들면서 진행하면 된다.

그리고 문제에서는 제일 마지막에 1을 모두 지우기 전 단계의 1의 개수를 구해야하므로
dfs 탐색 중 1을 마주쳤을 때 저장한 자료구조의 사이즈를 구하면 1의 개수를 구할 수 있다.

그런데 이때 언제 1의 위치를 저장하느냐에 따라 dfs 과정 중 1을 중복 방문하여
1의 개수를 제대로 구하지 못할 수 있다.

void dfs(int y, int x)
{
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx] == 1)
            continue;
            
        if (arr[ny][nx] == 1)
    	{
        	cheese.push_back({ny, nx});
    	}
        else
        	dfs(ny, nx);
    }
    return;
}

만약 다음과 같이 앞으로 방문할 위치가 1인지를 먼저 판단 후 해당 위치를 저장하면
0을 탐색하는 과정에서 1을 다시 방문하게 되어 중복 방문할 수 있게 된다.

따라서 다음 위치를 미리 확인한 경우에도 visited 를 1로 만들거나
다음 위치에 갔을 때 1인지 확인을 하고 return 을 해서 중복 방문을 막아야 한다.

void dfs(int y, int x)
{
    visited[y][x] = 1;
    
    // 방문하고 1인지 확인 후 return
    if (arr[ny][nx] == 1)
    {
    	cheese.push_back({ny, nx});
    	visited[ny][nx]
    }

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx] == 1)
            continue;
        
        // 미리 확인 후 방문도 표시
        // if (arr[ny][nx] == 1)
    	// {
        	// cheese.push_back({ny, nx});
            // visited[ny][nx]
    	// }
        // else
        	dfs(ny, nx);
    }
    return;
}

트리 탐색 with DFS

https://www.acmicpc.net/problem/1068

트리 탐색을 dfs 로 구현할 수 있는데 계속 해서 DFS 특성상 계속해서 더 깊은 레벨로 들어가는데
(dfs 생각이 안나서 preorder 재귀 로 하려다가 너무 코드가 꼬여버렸다...)

배열과 같은 그래프와 달리 트리에서는 계속 해서 자식 노드로 들어가기만 하면 되기 때문에
visited를 사용할 필요도 없다.

위의 문제는 트리 탐색을 통해 리프 노드의 개수를 구하는 문제로
노드를 지울 경우 해당 노드에 도달한 경우 더 이상 탐색을 진행하지 않으면 된다.

int dfs(int here)
{
    int ret = 0;
    int child = 0;
    for (int there : adj[here])
    {
        if (there == del_N)
            continue;
        ret += dfs(there);
        child++;
    }

    if (child == 0)
        return 1;
    else
        return ret;
}

위의 방법처럼 노드에 해당하는 adj[here] 를 통해 자식 노드들에 대한 재귀로
계속 탐색을 이어갈 수 있고 child 로 자식 노드의 개수를 새는 등의 동작을 추가하면 된다.

트리 탐색에서는 익숙한 DFS 를 생각해보자!