본문 바로가기

BOJ/C++

[BOJ] 구슬탈출2

[문제]

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드

www.acmicpc.net

[풀이]

13460 맞았습니다!! 2004 KB 0 ms C++14 / 수정 2856 B 26분 전

 

1) 기울인다. (한 칸씩 이동한다X) 

 

2) 두 구슬이 동시에 구멍에 빠지면 안된다. 

 

3) 두 구슬이 방문한 곳을 visited로 표시해서 반복을 줄인다. 

 

4) 큐에는 두 구슬의 좌표를 동시에 넣고 동시에 움직여야 한다. 

 

5) 외곽은 전부 #로 둘러싸여져 있기 때문에 따로 범위 체크를 하지 않아도 된다. 

 

6) 두 구슬이 겹치는 경우가 있다. 

-> 더 먼 곳에서 출발한 구슬을 뒤로 물러준다.

(다양한 방법이 있겠지만..)

 

7) 기울인 횟수가 10번을 초과하면 -1을 출력하고 종료한다. 

 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <queue>
#include <climits>
#include <cmath>
using namespace std;
 
//구슬탈출2
/*
    빨간 구슬이 구멍에 빠졌을 때만 성공 
    동시에 빠지면 안됨 
 
 */
typedef struct Biz
{
    int x, y;
    Biz(){};
    Biz(int _x, int _y) : x(_x), y(_y) {}
};
 
typedef struct Biz_q
{
    Biz r, b;
 
    Biz_q(){};
    Biz_q(Biz _x, Biz _y) : r(_x), b(_y){}
};
 
int n, m, ans = INT_MAX;
char map[11][11];
bool visited[11][11][11][11];
int dx[4= {00-11};
int dy[4= {-1100};
 
Biz red, blue;
pair<intint> hole;
 
int bfs()
{
    queue<Biz_q> q;
    q.push(Biz_q(red, blue));
    visited[red.x][red.y][blue.x][blue.y] = true;
    //red, blue가 동시에 움직여야 한다.
 
    int cnt = 0;
    while (!q.empty())
    {
        int size = q.size();
    
        while (size--)
        {
            Biz_q now = q.front();
            q.pop();
 
            Biz r_pos = now.r;
            Biz b_pos = now.b;
 
            if (map[r_pos.x][r_pos.y] == 'O' && map[r_pos.x][r_pos.y] != map[b_pos.x][b_pos.y] ){
                
                return cnt;
            }
 
            for (int i = 0; i < 4; i++)
            {
                Biz nr_pos = r_pos;
                Biz nb_pos = b_pos;
 
                while (map[nr_pos.x + dx[i]][nr_pos.y + dy[i]] != '#' && map[nr_pos.x][nr_pos.y] != 'O')
                {
                    //#이 아닐 때까지 움직임('기울이기' 이기 때문에 한 칸씩 움직일 수 없다. )
                    nr_pos.x += dx[i];
                    nr_pos.y += dy[i];
                }
                while (map[nb_pos.x + dx[i]][nb_pos.y + dy[i]] != '#' && map[nb_pos.x][nb_pos.y] != 'O')
                {
                    //#이 아닐 때까지 움직임('기울이기' 이기 때문에 한 칸씩 움직일 수 없다. )
                    nb_pos.x += dx[i];
                    nb_pos.y += dy[i];
                }
                //두 구슬이 겹치는 경우 (한 구슬만 움직이도록 해야한다. )
                if (nr_pos.x == nb_pos.x && nr_pos.y == nb_pos.y)
                {
                    if (map[nr_pos.x][nr_pos.y] == 'O'continue;
                    //동시에 구멍으로 가면 안됨 
                    if (abs(r_pos.x - nr_pos.x) + abs(r_pos.y - nr_pos.y) < abs(b_pos.x - nb_pos.x) + abs(b_pos.y - nb_pos.y))
                    {
                        //움직인 거리가 더 긴 쪽을 뒤로 물러준다.
                        nb_pos.x -= dx[i];
                        nb_pos.y -= dy[i];
                    }
                    else
                    {
                        //움직인 거리가 더 긴 쪽을 뒤로 물러준다.
                        nr_pos.x -= dx[i];
                        nr_pos.y -= dy[i];
                    }
                }
                if (visited[nr_pos.x][nr_pos.y][nb_pos.x][nb_pos.y])
                    continue;
 
                q.push(Biz_q(nr_pos, nb_pos));
                visited[nr_pos.x][nr_pos.y][nb_pos.x][nb_pos.y] = true;
            }
        } //while size
        if (cnt == 10) {
            
            return -1;
        }
        cnt++;
 
    }     //while q
    return -1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
 
            if (map[i][j] == 'R')
            {
                red.x = i;
                red.y = j;
 
            
            }
            if (map[i][j] == 'B')
            {
                blue.x = i;
                blue.y = j;
 
            
            }
        }
    }
    //입력 (#: wall/ . : empty)
    cout << bfs() << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

 

[코드 수정 버전]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//풀이 : 55분 

//구슬탈출2
/*
    빨간 구슬이 구멍에 빠졌을 때만 성공 
    동시에 빠지면 안됨 
 
 */

int n, m, ans = 10;
char map[11][11];
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;

pp hole, blue, red;

bool visited[11][11][11][11];

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};

int playGame()
{
    queue<pppp> q;
    q.push(pppp(red, blue));

    int cnt = 0;

    while (!q.empty())
    {
        int size = q.size();

        while (size--)
        {

            pp rPos = q.front().first;
            pp bPos = q.front().second;
            q.pop();

            if (map[rPos.first][rPos.second] == 'O' && map[rPos.first][rPos.second] != map[bPos.first][bPos.second])
            {
                return cnt;
            }
            //기울이기

            for (int i = 0; i < 4; i++)
            {
                int r_nx = rPos.first;
                int r_ny = rPos.second;
                int b_nx = bPos.first;
                int b_ny = bPos.second;

                while (map[r_nx + dx[i]][r_ny + dy[i]] != '#' && map[r_nx][r_ny] != 'O')
                {
                     //#이 아닐 때까지 움직임('기울이기' 이기 때문에 한 칸씩 움직일 수 없다. )
                    r_nx += dx[i];
                    r_ny += dy[i];
                }
                while (map[b_nx + dx[i]][b_ny + dy[i]] != '#' && map[b_nx][b_ny] != 'O')
                {
                     //#이 아닐 때까지 움직임('기울이기' 이기 때문에 한 칸씩 움직일 수 없다. )
                    b_nx += dx[i];
                    b_ny += dy[i];
                }

                 //두 구슬이 겹치는 경우 (한 구슬만 움직이도록 해야한다. )
                if (r_nx == b_nx && r_ny == b_ny)
                {
                    if (map[r_nx][r_ny] == 'O')
                    {
                        continue;
                    }
                    //동시에 같은 좌표에 있으면 안된다.
                    //더 멀리서 온 구슬을 뒤로 보낸다.
                    if (abs(rPos.first - r_nx) + abs(rPos.second - r_ny) > abs(bPos.first - b_nx) + abs(bPos.second - b_ny))
                    {
                        //빨간 구슬을 한 칸 뒤로 보냄
                        r_nx -= dx[i];
                        r_ny -= dy[i];
                    }
                    else
                    {
                        b_nx -= dx[i];
                        b_ny -= dy[i];
                    }
                }

                if (visited[r_nx][r_ny][b_nx][b_ny])
                    continue;
                q.push(pppp(pp(r_nx, r_ny), pp(b_nx, b_ny)));
                visited[r_nx][r_ny][b_nx][b_ny] = true;
            }
        } //while size

        if (cnt == 10)
        {
            return -1;
        }
        cnt++;
    }
    return -1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'R')
                red = pp(i, j);
            else if (map[i][j] == 'B')
                blue = pp(i, j);
        }
    }
    //input

    

    cout << playGame() << '\n';
    return 0;
}

'BOJ > C++' 카테고리의 다른 글

[BOJ] 시험감독  (0) 2019.08.07
[BOJ] 연산자 끼워넣기  (0) 2019.08.07
[BOJ] 연구소  (0) 2019.08.06
[BOJ] 로봇청소기  (0) 2019.08.06
[BOJ] 치킨배달  (0) 2019.08.06