골랜디 #9 2206번

Published at: 2025-03-27

Last modified at: 2025-03-27

오늘 푼 문제

안녕하세요 한라나입니다.
오늘은 모교에 놀러와서 온김에 문제를 풀었습니다.
원래는 술취한상태로 풀 계획이었는데, 이 문제를 술취하고 봤으면 골랜디 스트릭이 터졌을것 같습니다.ㅋㅋ
오늘 문제는 아래와 같습니다.

백만년만에 보는 bfs라니! 구현이 하나도 기억이 안 났어요.

요컨대 이 문제의 요지는 벽을 부순 상태로 방문했는지, 아직 안 부순 상태로 방문했는지 두 가지 경우의 visited 배열을 만드는 겁니다.
처음에 저는 주변에 0이 두 칸 이상 있는 벽만 부술 가치가 있다고 생각해서 그걸 구분해놨는데, 생각해보니까 필요 없겠더라구요.
추가로 int direction[4][2]를 만들면 코드가 우아해질텐데, 저는 귀찮?아서 if를 9개나 썼습니다.
이걸 하는 코드가 곧 전체 코드라서 코드는 아래를 보면 될 것 같습니다.

다녔던 고등학교, 다녔던 자리에서 골랜디라니 감회가 새롭네요.

감사합니다.

+제가 지금까지 c 컴파일러를 쓰고 있었네요… 큐 쓰자마자 터져나오는 오류가 무서웠습니다.
+그리고 입력이 왜이래?? 띄어쓰기 좀 해주지ㅠㅠㅠ
+코드 블럭 안에 있어도 중괄호 두개 겹쳐쓰면 오류나는거가 jekyll에서 유일하게 미운 점이네요…

---

전체 코드

#include <stdio.h>
#include <queue>

using namespace std;

int map[1010][1010];
int mark[1010][1010];
int visited[1010][1010][2];

queue< pair< pair< int, int >, pair< int, int > > > que;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int i, j;
    char line[1010];
    for(i=0;i<n+2;i++) {
        map[i][0] = 1;
        map[i][m+1] = 1;
    }
    for(i=0;i<m+2;i++) {
        map[0][i] = 1;
        map[n+1][i] = 1;
    }
    for(i=1;i<=n;i++) {
        scanf("%s", line);
        for(j=1;j<=m;j++) {
            map[i][j] = line[j-1] - '0';
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            if(map[i][j]==1) {
                if(map[i-1][j]+map[i+1][j]+map[i][j-1]+map[i][j+1]<=2) mark[i][j] = 1;
            }
        }
    }
    que.push({ {1, 0}, {1, 1} });
    while(!que.empty()) {
        auto k = que.front();
        que.pop();
        i = k.second.first;
        j = k.second.second;
        if((i==n)&&(j==m)) {
            printf("%d", k.first.first);
            return 0;
        }

        if((map[i+1][j]==0)&&(visited[i+1][j][k.first.second]==0)) {
            visited[i+1][j][k.first.second] = 1;
            que.push({ {k.first.first+1, k.first.second}, {i+1, j} });
        }
        if((map[i-1][j]==0)&&(visited[i-1][j][k.first.second]==0)) {
            visited[i-1][j][k.first.second] = 1;
            que.push({ {k.first.first+1, k.first.second}, {i-1, j} });
        }
        if((map[i][j+1]==0)&&(visited[i][j+1][k.first.second]==0)) {
            visited[i][j+1][k.first.second] = 1;
            que.push({ {k.first.first+1, k.first.second}, {i, j+1} });
        }
        if((map[i][j-1]==0)&&(visited[i][j-1][k.first.second]==0)) {
            visited[i][j-1][k.first.second] = 1;
            que.push({ {k.first.first+1, k.first.second}, {i, j-1} });
        }

        if(k.first.second==0) {
            if((mark[i+1][j]==1)&&(visited[i+1][j][1]==0)) {
                visited[i+1][j][1] = 1;
                que.push({ {k.first.first+1, 1}, {i+1, j} });
            }
            if((mark[i-1][j]==1)&&(visited[i-1][j][1]==0)) {
                visited[i-1][j][1] = 1;
                que.push({ {k.first.first+1, 1}, {i-1, j} });
            }
            if((mark[i][j+1]==1)&&(visited[i][j+1][1]==0)) {
                visited[i][j+1][1] = 1;
                que.push({ {k.first.first+1, 1}, {i, j+1} });
            }
            if((mark[i][j-1]==1)&&(visited[i][j-1][1]==0)) {
                visited[i][j-1][1] = 1;
                que.push({ {k.first.first+1, 1}, {i, j-1} });
            }
        }
    }
    printf("-1");
    return 0;
}