본문 바로가기

백준 문제 풀이

 (148)
백준 7576번 토마토(C++) 예전에 풀었던 문제이지만 다시한 번 해보았다. 예전의 코드는 구글링의 다른 사람의 코드를 도움 받았기 때문이다. 그리고 BFS의 좋은 예제이다. 먼저 토마토 1이 있으면 하루에 4방향으로 증식한다. 증식한 토마토는 또 4방향으로 증식하게된다. DFS로 계산하면 한 방향으로만 가버리기 때문에 적절하지 않다. 결국 BFS를 통해 첫 1부터 제일 떨어져 있는 거리까지의 최소거리(최소일수)를 구하는 문제로 귀결된다. 그러나 여기서 중요한 것은 1이 한군데만 존재하지 않는다는 것이다. 즉, 두군데 이상의 1에서 동시에 증식을 시작해야한다. 그림으로 표현하면 이런식이다. 때문에 DFS는 절대(적어도 내 기준에선) 사용할 수 없다. 알고리즘은 이러하다. 1. 처음 토마토가 심어져 있는 좌표를 큐에 삽입. 2. 삽입된..
백준 1697 숨바꼭질 (C++) #include #include #include #include #include #include #define MAX 51 using namespace std; queue Q; int x, y; bool visited[100001] = {false,}; void BFS() { Q.push(make_pair(x, 0)); visited[x] = true; while (!Q.empty()) { int X = Q.front().first; int T = Q.front().second; Q.pop(); if (X == y) { cout -1 && X - 1 < 100001 && visited[X - 1] == false) { Q.push(make_pair(X - 1, T + 1)); visited[X - 1] ..
백준 1707번 이분 그래프(C++) #include #include #include #define MAX 20001 using namespace std; int V, E; int x, y; int check = 0; vector vertex[MAX]; bool visited[MAX] = { false, }; int vertexCol[MAX] = { 0, }; void setgraph() { cin >> V >> E; for (int i = 0; i > x >> y; vertex[x].push_back(y); vertex[y].push_back(x); } } void DFS(int here) { if (visited[here] == true) return; visited[here] = true; for (int..
백준 1966번 프린터 큐(C++) #include #include #include #include using namespace std; int S, N, M; int x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> S; for (int i = 0; i > N >> M; int cnt = 0; for (int j = 0; j > x; Q.push(x); q.push(make_pair(j, x)); } while (!q.empty()) { int index = q.front().first; int value = q.front(..

티스토리툴바