13460 구슬 탈출 2 -BFS

1.문제

2.코드

#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
 
struct balls {
    int depth;
    int rx, ry, bx, by;
};
 
int irx, iry, ibx, iby, hx, hy;
bool visit[10][10][10][10];
int n, m, ans = -1;
int map[10][10];
char str[11];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
 
void move(int& x, int& y, int d)
{
    while (1)
    {
        x += dir[d][0]; y += dir[d][1];
        //벽에 부딪히면 후퇴하고 정지
        if (map[x][y] == 1)
        {
            x -= dir[d][0]; y -= dir[d][1];
            break;
        }
        //구멍을 만나면 정지
        else if (map[x][y] == 2)
            break;
    }
}
 
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", str);
        for (int j = 0; j < m; ++j)
        {
            switch (str[j])
            {
            case '.':
                map[i][j] = 0; break;
            case '#':
                map[i][j] = 1; break;
            case 'O':
                map[i][j] = 2; hx = i, hy = j; break;
            case 'R':
                irx = i, iry = j; break;
            case 'B':
                ibx = i, iby = j; break;
            }
        }
    }
 
    queue<balls> q;
    q.push({ 0,irx,iry,ibx,iby });
    visit[irx][iry][ibx][iby] = true;
    while (!q.empty())
    {
        balls cur = q.front(); q.pop();
        if (cur.depth > 10)
            break;
        if (cur.rx == hx && cur.ry == hy)
        {
            ans = cur.depth;
            break;
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int rx = cur.rx, ry = cur.ry;
            int bx = cur.bx, by = cur.by;
            move(rx, ry, i); move(bx, by, i);
 
            //파란공이 구멍에 들어가면 다른방향으로 다시. 
            //빨간공이 먼저 들어간다고 해도 파란공도 결국 들어가므로
            if (bx== hx && by == hy)
                continue;
            //파란공과 빨간공이 겹칠 경우
            if (rx == bx && ry == by)
            {
                switch (i)
                {
                case 0:
                    cur.rx < cur.bx ? rx-- : bx--; break;
                case 2:
                    cur.rx < cur.bx ? bx++ : rx++; break;
                case 1:
                    cur.ry < cur.by ? ry-- : by--; break;
                case 3:
                    cur.ry < cur.by ? by++ : ry++; break;
                }
            }
            if (!visit[rx][ry][bx][by])
            {
                balls next = { cur.depth + 1,rx,ry,bx,by };
                q.push(next);
                visit[rx][ry][bx][by] = true;
            }
 
        }
    }
    printf("%d", ans);
    return 0;
 
}
 

3. 후기

제출을 할 때, 내 코드를 제출하면 메모리와 시간이 어마어마하게 나오고, 블로그대로 제출하면 훨씬 줄어들었다. 그것 때문에 주석도 지워보고, 조금 다르게 한 부분을 완전 같도록 바꿔도 봤는데 결국 마지막 = true를 == true로 하는 바람에 그랬던 것이었다. 

처음에는 틀렸습니다가 나왔는데 이동횟수가 10을 넘었는지 확인하는 부분에서 cur.depth == 10로 했었다. 그랬더니 틀렸다고 나왔다. 10번까지는 허용이 되니까 10은 포함하면 안되는 거였다.