17267 상남자

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

17267번: 상남자

처음에는 BFS로 단순히 탐색해서 예제가 다 맞길래 제출해봤더니 틀렸습니다!

문제점이 세가지 있었다.

첫번째는 queue가 아닌 deque로 풀어야 한다는 것.

두번째는 오른쪽 왼쪽으로 갈 때 원래의 점 정보의 L, R 값을 함부로 줄이면 안된다는 점

마지막으로 x, y 방향 문제 (이건 아직도 헷갈린다 디버깅해서 겨우 적응)

 

첫번째 문제는

https://www.acmicpc.net/board/view/37868

글 읽기 - BFS문제. 맞았는데 왜 맞는거죠?!

(여기서 대단한 분이 기가막힌 반례를 주셨기 때문에)

상하좌우로 1칸씩 이동하면 못가게되는 곳이 생겨서, 문제처럼 최대한 상하좌우로 움직일 수 있게 queue가 아닌 deque로 짜야한다.

deque로 상하로 최대한 움직일 수 있게 로 앞쪽에 삽입하고, deque.push_front()

좌우로 움직이는 것은 큐 뒤쪽에 삽입한다. deque.push_back()

---

두번째 문제는 

if (i==3) {
	if (left>0)    p = {nx, ny, left -1, right};
    else    continue;
}
else if (i==1) {
	if (right>0)    p = {nx, ny, left, right - 1};
    else    continue;
}
else {
	p = {nx, ny, left, right};
}
                

이 부분에서 처음엔 

left--;

right--;

으로 줄인값을 넣었더니 다음 for문을 돌 때, 왼쪽 오른쪽을 가지 않았는데도 값이 줄어서 전달되기 때문에 잘못되었다.

 

 

전체코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
using namespace std;

struct pos{
    int x;
    int y;
    int left;
    int right;
};

int N, M, L, R, sx, sy, cnt;
int map[1000][1000];
bool visit[1000][1000];
deque<pos> q;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main(int argc, const char * argv[]) {
    string input;
    cin >> N >> M >> L >> R;
    for (int i=N-1; i>=0; i--) {
        cin >> input;
        for (int j=0; j<M; j++) {
            map[j][i] = input[j] - '0';
            if (map[j][i] == 2) {
                sx = j;
                sy = i;
            }
        }
    }
    
    pos p = {sx, sy, L, R};
    q.push_back(p);
    visit[sx][sy] = true;
    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int left = q.front().left;
        int right = q.front().right;
        q.pop_front();
        
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0<=nx && nx<M && 0<=ny && ny<N && map[nx][ny] != 1 && !visit[nx][ny]) {
                if (i==3) {
                    if (left>0)    p = {nx, ny, left -1, right};
                    else    continue;
                }
                else if (i==1) {
                    if (right>0)    p = {nx, ny, left, right - 1};
                    else    continue;
                }
                else {
                    p = {nx, ny, left, right};
                }
                
                if (i==0 || i==2) {
                    q.push_front(p);
                }
                else if (i==1 || i==3) {
                    q.push_back(p);
                }
                
                visit[nx][ny] = true;
            }
        }
    }
    
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            if (visit[i][j]) {
                cnt++;
            }
        }
    }
    
    cout << cnt << "\n";
    return 0;
}

 

 

 

주저리..

맥북 디버깅 완전 적응했다 이문제로...ㅎㅎ

deque는 디큐인가 덱인가 데큐인가