[C++] 백준 2206번: 벽 부수고 이동하기

🔗문제

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

2206번: 벽 부수고 이동하기

 

🖍풀이

 

내 기준 너무 너무 어려웠다. 결국 풀다가 검색의 힘을 빌렸고 참고하기 좋은 글을 첨부한다.

🔗 글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

 

MAX 1,000인데 실수로 10,000으로 설정해서 틀렸습니다를 엄청 봤다...

지금은 실전이 아님에 감사 + 덕분 소스 분석 열심히 한거에 의의를 ! 😭

 

Struct

struct Set
{
public:
    Set(int _x, int _y, bool _b = false)
        : x(_x), y(_y), b(_b) {};

    int x, y;
    bool b; // 이미 벽 부쉈으면 true
};

좌표와 벽 부숨 유무를 저장할 구조체를 생성해줬다.

 

std::queue<Set> q;
int visited[2][MAX][MAX]; // [벽뚫음유무][x][y]

q.push(Set(0, 0, false));
visited[0][0][0] = 1;

• (0, 0)에서 벽을 부수지 않고 시작한다는 정보를 구조체로 만들어 queue에 넣어준다.
• 시작 지점도 이동수에 포함하니 반드시 1이라는 값을 넣어준다.
  
  

BFS에서 중요한 부분

단순해 보여도 3차원이기 때문에 잘 보아야 한다.

if(map[x][y] == 0) // 막히지 않았다 
{
    q.push({x, y, b}); // 좌표와 현재 부숨 사용 여부 
    visited[b][x][y] = visited[b][nowX][nowY] + 1;
}
else if(map[x][y] == 1 && !b)
    q.push({x, y, 1});
    visited[1][x][y] = visited[b][nowX][nowY] + 1;
}

• 뚫린 공간
  • 현재 상태대로 값을 넣어주면 된다.
  • 벽을 한번 뚫었든 말든 뚫린 공간 지나가는데 상관 없다.
• 막힌 공간이고 아직 벽을 뚫지 않았다면
  • 벽을 뚫을 수 있는 기회는 단 한 번뿐이다.
  • 그 한 번의 기회를 써서 벽을 뚫어준다. (b = true)
  • 뚫린 경로가 되었으니 visited[1][x][y]에 다가 현재 상태에서 이동 횟수 1을 더 해주면 된다.

 

---

 

도움된 반례 + 3차원 배열을 쓴 이유

 

5%에서 메모리 초과를 봤다. (지옥의 메모리 초과)

백준에 있는 모든 반례를 싹싹 돌려봐도 정답이었는데 이 반례 하나가 큰 도움이 되었다.

원인은 특정 지역에 벽 부순 경우랑 벽 안 부순 경우가 동시에 방문하게 될 때가 하나만 저장되는 문제였다.

2 6
010001
000110
//정답: 9
//출력: -1

🔗 https://www.acmicpc.net/board/view/97633 (dong5995)

 

 

즉, 특정 좌표에서 벽을 부쉈을 경우와 부수지 않은 경우의 값을 다 저장하기 3차원을 사용해줬다.

visited[x][y] // 벽 부숨과 관련 없는 이동 수 

 

visited[0][x][y] // 벽을 부수지 않았을 때 이동 수
visited[1][x][y] // 벽을 부쉈을 때 이동 수

 

💾 소스

#include <iostream>
#include <queue>
#define MAX 1001

int N,M;
int map[MAX][MAX];

struct Set
{
public:
    Set(int _x, int _y, bool _b = false)
        : x(_x), y(_y), b(_b) {};

    int x, y;
    bool b; // 이미 벽 부쉈으면 true
};

bool isValid(int a, int b)
{
    if(a>=N || b>=M || a<0 || b<0 || a>MAX || b>MAX)
        return false;
    return true;
}

int BFS()
{
    std::queue<Set> q;
    int visited[2][MAX][MAX];

    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    
    visited[0][0][0] = 1;
    q.push(Set(0, 0, false));
    
    while(!q.empty())
    {
        int nowX = q.front().x;
        int nowY= q.front().y;
        bool b = q.front().b;
        q.pop();
        
        if(nowX==N-1 && nowY == M-1)
            return visited[b][nowX][nowY];
        
        for(int i=0; i<4; ++i)
        {
            int x = nowX + dx[i];
            int y = nowY + dy[i];
            
            if(!isValid(x, y) || visited[b][x][y]!=0)
                continue;
            
            if(map[x][y] == 0)
            {
                q.push({x, y, b});
                visited[b][x][y] = visited[b][nowX][nowY] + 1;
            }
            else if(map[x][y] == 1 && !b)
            {
                q.push({x, y, 1});
                visited[1][x][y] = visited[b][nowX][nowY] + 1;
            }
        }
    }
    
    return -1;
}

int main()
{
    char in;
    std::cin >> N >> M;
    for(int i=0; i<N; ++i) {
        for(int j=0; j<M;++j) {
            std::cin >> in;
            map[i][j] = in - '0';
        }
    }

    std::cout << BFS();
    
    return 0;
}