백준 17837 [4%에서 틀렸습니다.]

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

17837번: 새로운 게임 2

https://youtu.be/fAs85oVcu1g

접근법은 위 동영상과 동일하다.

말의 위치를 나타내는 node_map[][]과

말의 정보를 나타내는 node_arr[]를 사용했다.

하지만 구현을 잘 못해서 그런지, 4%에서 틀렸습니다가 계속 떴다

테스트 케이스 5개는 모두 맞게 나오고 질문 게시판도 다 읽어봤는데 원인을 못 찾았다...

 

5번 테스트 케이스의 진행과정

---

01234567

진행과정은 백준 게시판에 있는 설명과 동일하다

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

글 읽기 - test 케이스별 참고자료

질문 게시판에서 4%에서 틀렸습니다가 뜬다는 글을 읽어보면 배열 범위 문제인 것 같은데,

배열 범위도 넉넉하게 잡았고, 범위 체크도 다 한 것 같은데...

 

파란색 혹은 벽을 만났을 때 반대 방향으로 이동 시, 반대 방향의 색 (흰 / 빨강 / 파랑)도 체크했고,

빨간색 칸에 기존 말이 존재할 경우, 기존 말의 순서는 바뀌지 않고 새로 이동한 말의 순서만 뒤집는 것도 체크했다.

 

소스코드 (4%에서 틀렸습니다.)

---

#include <iostream>
#include <vector>
#include <stack>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct Node {
    int i, j, d, idx;
};
int dx[] = { -1, 0, 0, -1, 1 };
int dy[] = { -1, 1, -1, 0, 0 };
int n, k;
int arr[13][13];
vector<int> node_map[13][13];
Node node_arr[11];
stack<int> s;
void input();
void changeDirection(Node &now) {
    if (now.d == 1) now.d = 2;
    else if (now.d == 2) now.d = 1;
    else if (now.d == 3) now.d = 4;
    else if (now.d == 4) now.d = 3;
}
int func() {
    int cnt = 1;
    while (cnt <= 1000) {
        rep(i, k) {
            // 지금 이동시킬 말이 몇 번째 칸에서 몇 번째 순서인지 확인하기
            Node start = node_arr[i];
            int x = start.i;
            int y = start.j;
 
            // 현재 말 위에 쌓여있는 것들은 현재 말의 방향 따라 움직임
            int nx = x + dx[start.d];
            int ny = y + dy[start.d];
 
            bool added = true;
            // 현재 말의 위치에서 현재 말보다 뒤에 (위에) 있는 것들은 다 같이 이동시키기
        
            for (int idx = start.idx; idx < node_map[x][y].size(); idx++) {
                int node_num = node_map[x][y][idx];
                Node &now = node_arr[node_num];
 
                // 다음 칸이 벽 또는 파란색
                if (nx<1 || nx>n || ny<1 || ny>n || arr[nx][ny] == 2) {
                    changeDirection(now);
                    
                    nx = now.i + dx[now.d];
                    ny = now.j + dy[now.d];
                    
                    // 이동할 칸이 파란색이면 정지
                    if (nx<1 || nx>n || ny<1 || ny>n || arr[nx][ny] == 2) {
                        added = false;
                        break;
                    }
                }
                // 위치 이동
                now.i = nx;
                now.j = ny;
                
                // 다음 칸이 흰 색
                if (arr[nx][ny] == 0) {
                    now.idx = node_map[nx][ny].size();
                    node_map[nx][ny].push_back(node_num);
                }
 
                // 다음 칸이 빨간 색
                else if (arr[nx][ny] == 1) {
                    // 순서 뒤집어야함
                    s.push(node_num);
                }
 
                // 이동시킨 칸에 말이 4개 쌓이면 즉시 종료
                if (node_map[nx][ny].size() >= 4)
                    return cnt;
            }
 
            // 빨간색일 경우 처리
            while (!s.empty()) {
                int now = s.top(); s.pop();
                node_arr[now].idx = node_map[nx][ny].size();
                node_map[nx][ny].push_back(now);
            }
 
            // 기존 칸에서 지우기
            while (added&&node_map[x][y].size() > start.idx)
                node_map[x][y].erase(node_map[x][y].begin() + start.idx);
        }
        cnt++;
    }
    return cnt;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    int ret = func();
    cout << (ret > 1000 ? -1 : ret);
}
void input() {
    cin >> n >> k;
    rep(i, n) {
        rep(j, n)
            cin >> arr[i][j];
    }
    rep(i, k) {
        Node node;
        cin >> node.i >> node.j >> node.d;
        node.idx = 0;
        node_arr[i] = node;
        node_map[node.i][node.j].push_back(i);
    }
}