티스토리 뷰

알고리즘 관련/BOJ

BOJ)13460 구슬탈출2

JASON 자손9319 2017. 3. 30. 16:45

문제: icpc.me/13460


빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다.


우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다.


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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, disc[11][11][11][11], bx, by, rx, ry;
char a[11][11];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
int bfs() {
    queue<pair<pair<intint>, pair<int,int>>> qu;
    qu.push({ {rx,ry},{bx,by} });
    disc[rx][ry][bx][by] = 1;
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int x = qu.front().first.first;
            int y = qu.front().first.second;
            int z = qu.front().second.first;
            int w = qu.front().second.second;
            qu.pop();
            if (a[x][y] == 'O'&&a[x][y] != a[z][w])
                return ret;
            for (int i = 0; i < 4; i++) {
                int cx = x, cy = y, cz = z, cw = w;
                while (a[cx + dx[i]][cy + dy[i]] != '#'&&a[cx][cy] != 'O') {
                    cx += dx[i];
                    cy += dy[i];
                }
                while (a[cz + dx[i]][cw + dy[i]] != '#'&&a[cz][cw] != 'O') {
                    cz += dx[i];
                    cw += dy[i];
                }
                if (cx == cz&&cy == cw) {
                    if (a[cx][cy] == 'O')continue;
                    if (abs(cx - x) + abs(cy - y) < abs(cz - z) + abs(cw - w)) {
                        cz -= dx[i];
                        cw -= dy[i];
                    }
                    else {
                        cx -= dx[i];
                        cy -= dy[i];
                    }
                }
                if (disc[cx][cy][cz][cw])continue;
                qu.push({ {cx,cy} ,{cz,cw} });
                disc[cx][cy][cz][cw] = 1;
            }
        }
        if (ret == 10)
            return -1;
        ret++;
    }
    return -1;
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c"&a[i][j]);
            if (a[i][j] == 'B') {
                bx = i;
                by = j;
            }
            else if (a[i][j] == 'R') {
                rx = i;
                ry = j;
            }
        }
    }
    printf("%d\n", bfs());
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1058 친구  (0) 2017.04.03
BOJ)12100 2048 (Easy)  (0) 2017.03.30
BOJ)13460 구슬탈출2  (6) 2017.03.30
BOJ)1520 내리막 길  (0) 2017.03.30
BOJ)10422 괄호  (0) 2017.03.30
BOJ)1194 달이 차오른다, 가자.  (0) 2017.03.30
TAG
댓글
  • 프로필사진 반함 와..본것중에 제일 깔끔해요!! 많이 배워갑니다 감사합니다:) 2018.04.11 23:46
  • 프로필사진 JASON 자손9319 감사합니다 !! .. 2018.04.14 00:50 신고
  • 프로필사진 반함2 진짜 코드 완전 이해하기 좋은 거 같아요 많이 배워갑니다!! :) 2019.03.05 22:36
  • 프로필사진 반함3 제일 깔끔!! 2019.03.08 11:13
  • 프로필사진 보롬 #include <iostream>
    #include <algorithm>

    using namespace std;


    int n, m;
    char map[10][10] = { 0, };


    int ans;
    int Min = 11;
    int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
    int hx, hy;


    void go(int cnt, int pre, int rx, int ry, int bx, int by) {

    int r_ch = 0, b_ch = 0; //빨간공과 파란공이 구멍에 들어간 경우 1로 초기화
    int i, j;
    int n_rx, n_ry, n_bx, n_by;



    //최소를 넘기면 리턴
    if (cnt >= Min) //이미 구해진 최소보다 크다면 더 구할 필요 없다.
    return;

    //****************우선순위!!!!!!!

    //움직임 명령에 따라 빨간공과 파란공 움직임.

    n_rx=rx, n_ry=ry, n_bx=bx, n_by=by;

    while (1) {
    if (map[n_rx + dx[pre]][n_ry + dy[pre]] == '#') {
    break;
    }
    else {
    n_rx = n_rx + dx[pre];
    n_ry = n_ry + dy[pre];
    }

    if (n_rx == hx && n_ry == hy) {
    r_ch = 1; //빨간공이 구멍에 들어감}
    break; //반복문 탈출
    }
    }

    while (1) {
    if (map[n_bx + dx[pre]][n_by + dy[pre]] == '#') {
    break; //만약 벽이라면 반복문 탈출
    }
    else {
    n_bx = n_bx + dx[pre];
    n_by = n_by + dy[pre];
    }

    if (n_bx == hx && n_by == hy)
    b_ch = 1; //빨간공이 구멍에 들어감
    }


    if (b_ch == 1) //빨간공과 함께 파란공이 들어간 경우와 파란공 혼자 들어간 경우 모두 false
    return;
    else if (r_ch == 1) {//빨간공만 들어간 경우
    Min = min(Min, cnt); //최솟값인지 확인후 리턴
    return;
    }


    if (n_rx == n_bx && n_ry == n_by) { //같은 위치에 있는경우
    if (abs(rx - n_rx) + abs(ry - n_ry) > abs(bx - n_bx) + abs(by - n_by)) { //더 많이 움직인 애가 위치를 바꿔야 한다.
    n_rx -= dx[pre];
    n_ry -= dy[pre];
    }
    else {
    n_bx -= dx[pre];
    n_by -= dy[pre];
    }
    }

    rx = n_rx, ry = n_ry, bx = n_bx, by = n_by;


    if (pre == 0 || pre == 1) {

    go(cnt + 1, 2,rx,ry,bx,by);

    go(cnt + 1, 3, rx, ry, bx, by);

    }
    else if (pre == 2 || pre == 3) {

    go(cnt + 1, 0, rx, ry, bx, by);

    go(cnt + 1, 1, rx, ry, bx, by);

    }
    }


    int main() {

    cin >> n >> m;

    int rx, ry, bx, by;

    for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    cin >> map[i][j];
    if (map[i][j] == 'B')
    bx = i, by = j;
    else if (map[i][j] == 'R')
    rx = i, ry = j;
    else if (map[i][j] == 'O')
    hx = i, hy = j;
    }
    }

    go(1, 0, rx, ry, bx, by);

    go(1, 1, rx, ry, bx, by);

    go(1, 2, rx, ry, bx, by);

    go(1, 3, rx, ry, bx, by);


    if (Min == 11)
    cout << -1;
    else
    cout << Min;


    //system("pause");
    }


    저는 DFS로 풀어봤어요
    덕분에 겹치는 부분에서 어케 해결해야할지 고민이였는데
    너무 쉽게 코딩해주셔서 많은 도움이 됐어요!!
    감사합니다.
    2019.05.28 15:28
  • 프로필사진 깔끔한 코드에 감동 받고 갑니닷 2019.11.20 22:34
댓글쓰기 폼