2194 유닛 이동시키기

DFS로 슥삭하면 해결할 수 있을 것 같은데

 

명시적으로 그래프가 주어지지 않았으니 배열로 구현해야겠다. 

 

 

---

ㅋㅋㅋ 위에 bfs로 구현한다고 해놓고선 dfs로 구현했다. 

어쩐지 길이가 22 나오더라

bool dfs(int x, int y, int len)
{
    if (visited[x][y] || maps[x][y] == '.')
        return false;

    visited[x][y] = true;
    len++;
    if (x == endx && y == endy)
        return true;
    
    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] > 0 && y + dy[i] > 0 && y + dy[i] <= m && x + dx[i] <= n)
            dfs(x + dx[i], y + dy[i], len);
    }
}

 

 

헉 bfs도 22나오는데

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

bool visited[505][505];
char maps[505][505];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

int n, m, a, b, endx, endy;

int     main()
{
    int k;
    scanf("%d %d %d %d %d", &n, &m, &a, &b, &k);

    for (int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        maps[x][y] = '.';
    }

    int startx, starty;
    scanf("%d %d", &startx, &starty);
    scanf("%d %d", &endx, &endy);

    int len = 0;

    queue<ii> Q;
    Q.emplace(startx, starty);
    visited[startx][starty] = true;

    while (!Q.empty())
    {
        ii curr = Q.front();
        Q.pop();
        printf("%d %d %d\n", curr.xx, curr.yy, len);

        if (maps[curr.xx][curr.yy] == '.')
            continue;
        
        if (curr.xx == endx && curr.yy == endy)
        {
            printf("find! %d\n", len);
            break;
        }
        
        for (int i = 0; i < 4; i++)
        {
            ii next;
            next.xx = curr.xx + dx[i];
            next.yy = curr.yy + dy[i];

            if (next.xx <= 0 || n < next.xx)
                continue;
            if (next.yy <= 0 || m < next.yy)
                continue;

            if (!visited[next.xx][next.yy])
            {
                visited[next.xx][next.yy] = true;
                Q.emplace(next.xx, next.yy);
            }
        }

        len++;
    }

    return 0;
}

 

알고보니 위와 같은 방법으로는 높이를 구할 수 없고 따로 배열을 추가해서 높이를 기록해놔야한다. 

뭔가 디피 같았다.

 

이제 높이도 어떻게 제는지 알았고 이제 a * b 크기만 해결하면 된다.

 

단순히 오른쪽으로 갈 때만 확인하려고 했는데 위쪽으로 올라갈때도 닿는 부분이 있는지 없는지 확인해야 하므로 따로 함수를 만들었다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool visited[505][505];
char maps[505][505];
int h[505][505];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

int n, m, a, b, endx, endy;

bool    check_square(int x, int y)
{
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            if (maps[x + i][y + j] == '.')
                return true;
        }
    }
    return false;
}

int     main()
{
    int k;
    scanf("%d %d %d %d %d", &n, &m, &a, &b, &k);
    n++, m++;

    for (int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        maps[x][y] = '.';
    }

    int startx, starty;
    scanf("%d %d", &startx, &starty);
    scanf("%d %d", &endx, &endy);

    queue<ii> Q;
    Q.emplace(startx, starty);
    visited[startx][starty] = true;

    int ans = -1;
    while (!Q.empty())
    {
        ii curr = Q.front();
        Q.pop();

        //printf("%d %d\n", curr.xx, curr.yy);

        if (curr.xx == endx && curr.yy == endy)
        {
            ans = h[curr.xx][curr.yy];
            break;
        }
        
        for (int i = 0; i < 4; i++)
        {
            ii next;
            next.xx = curr.xx + dx[i];
            next.yy = curr.yy + dy[i];

            if (next.xx <= 0 || n < next.xx + a)
                continue;
            if (next.yy <= 0 || m < next.yy + b)
                continue;

            if (visited[next.xx][next.yy])
                continue;

            if (check_square(next.xx, next.yy))
                continue;

            visited[next.xx][next.yy] = true;
            h[next.xx][next.yy] = h[curr.xx][curr.yy] + 1;
            Q.emplace(next.xx, next.yy);
        }
    }

    printf("%d\n", ans);

    return 0;
}

 

회고

 

이 문제의 어느 부분을 보고 bfs를 떠올렸는가?

 

s에서 한 칸씩 이동하면서 e로 가는 걸 보니 bfs, dfs가 떠올랐다. 

저번에 양치기 꿍 문제를 풀 때 dfs로 풀었는데 이 문제 푼 경험으로, 배열이 주어지고 이 배열을 한 칸 씩 칠하는 문제 = bfs? dfs로 풀면 어떨까? 로 사고과정이 흐른듯

 

다음으로 s에서 e까지의 최소 이동 횟수를 구하라고 했으니 bfs로 풀면 되겠다 싶었다.