백준[13460] - 구슬 탈출 2

문제

백준 13460 문제 보기

접근 방법

코드를 줄이는 습관을 들여야겠다. 문제는 모든 방향에 대해서 10번을 수행한뒤 안되면 -1을 출력하면 된다.

1. 노드 구조체를 만들어 빨간색, 파란색 구슬을 관리한다.
2. 각 방향 별로 구슬을 벽까지 이동시키고 빨간 구슬과 파란 구슬의 위치를 봐서 상관 관계를 구현한다.
3. 파란 구슬과 빨간 구슬이 동시에 들어갔을 경우를 예외처리한다.
4. 노드 객체 안에 cnt를 증가시키고 변경된 위치를 큐에 집어 넣는다.
5. cnt가 10보다 크거나 작으면 -1을 출력한다.

코드

#include <iostream>
#include <queue>

using namespace std;

struct node {
    int redR;
    int redC;
    int blueR;
    int blueC;
    int redGoal = 0;
    int blueGoal = 0;
    int cnt = 0;
};

int N, M;
int map[11][11];
queue q;

int main() {
    cin >> N >> M;

    char c;
    node n;
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < M; j ++) {
            cin >> c;

            if(c == '#') {
                // 벽은 -1로 저장
                map[i][j] = - 1;
            } else if (c == '.') {
                // 길은 0으로 저장
                map[i][j] = 0;
            } else if(c == 'O') {
                // 출구는 1로 저장
                map[i][j] = 1;
            } else if(c == 'R') {
                // 빨간 구슬 위치 저장
                n.redR = i;
                n.redC = j;
            } else {
                // 파란 구슬 위치 저장
                n.blueR = i;
                n.blueC = j;
            }
        }
    }

    // 큐에 삽입
    q.push(n);

    while(!q.empty()){
        // cnt가 10보다 크거나 같으면 탈출
        if(q.front().cnt >= 10)
            break;

        // 4방향에 대해서 큐에 삽입
        for (int dir = 0; dir < 4; dir++) {
            // 북
            if (dir == 0) {
                node temp = q.front();
                // 새롭게 위치한 빨간 구슬과 파란 구슬의 row값
                int redNR = temp.redR;
                int blueNR = temp.blueR;
                // 빨간 구슬 벽으로 이동
                while (map[redNR - 1][temp.redC] != -1) {
                    // 출구라면 이동을 중단하고 탈출
                    if (map[redNR - 1][temp.redC] == 1) {
                        temp.redGoal = 1;
                        break;
                    }
                    redNR--;
                }
                // 파란 구슬 벽으로 이동
                while (map[blueNR - 1][temp.blueC] != -1) {
                    if (map[blueNR - 1][temp.blueC] == 1) {
                        temp.blueGoal = 1;
                        break;
                    }
                    blueNR--;
                }
                // 빨간 구슬과 파란 구슬의 위치가 같으면 이전 위치에서 상관 관계를 봐 위치를 조정
                if (temp.blueC == temp.redC && redNR == blueNR) {
                    if (temp.redR < temp.blueR) {
                        blueNR++;
                    } else {
                        redNR++;
                    }
                }
                // 빨간 구슬만 골인 했다면 정답 출력
                if (temp.blueGoal == 0 && temp.redGoal == 1) {
                    cout << temp.cnt + 1;
                    return 0;
                }
                // 빨간 구슬과 파란 구슬이 아직 골인이 아니라면 cnt를 증가시키고 위치를 바꾼 다음 큐에 삽입
                if (temp.blueGoal == 0 && temp.redGoal == 0) {
                    temp.cnt++;
                    temp.blueR = blueNR;
                    temp.redR = redNR;
                    q.push(temp);
                }
            } 
            // 남
            else if (dir == 1) {
                node temp = q.front();
                int redNR = temp.redR;
                int blueNR = temp.blueR;
                while (map[redNR + 1][temp.redC] != -1) {
                    if (map[redNR + 1][temp.redC] == 1) {
                        temp.redGoal = 1;
                        break;
                    }
                    redNR++;
                }
                while (map[blueNR + 1][temp.blueC] != -1) {
                    if (map[blueNR + 1][temp.blueC] == 1) {
                        temp.blueGoal = 1;
                        break;
                    }
                    blueNR++;
                }
                if (temp.blueC == temp.redC && redNR == blueNR) {
                    if (temp.redR < temp.blueR) {
                        redNR--;
                    } else {
                        blueNR--;
                    }
                }
                if (temp.blueGoal == 0 && temp.redGoal == 1) {
                    cout << temp.cnt + 1;
                    return 0;
                }
                if (temp.blueGoal == 0 && temp.redGoal == 0) {
                    temp.cnt++;
                    temp.blueR = blueNR;
                    temp.redR = redNR;
                    q.push(temp);
                }
            } 
            // 서
            else if (dir == 2) {
                node temp = q.front();
                int redNC = temp.redC;
                int blueNC = temp.blueC;
                while (map[temp.redR][redNC - 1] != -1) {
                    if (map[temp.redR][redNC - 1] == 1) {
                        temp.redGoal = 1;
                        break;
                    }
                    redNC--;
                }
                while (map[temp.blueR][blueNC - 1] != -1) {
                    if (map[temp.blueR][blueNC - 1] == 1) {
                        temp.blueGoal = 1;
                        break;
                    }
                    blueNC--;
                }
                if (temp.blueR == temp.redR && redNC == blueNC) {
                    if (temp.redC < temp.blueC) {
                        blueNC++;
                    } else {
                        redNC++;
                    }
                }
                if (temp.blueGoal == 0 && temp.redGoal == 1) {
                    cout << temp.cnt + 1;
                    return 0;
                }
                if (temp.blueGoal == 0 && temp.redGoal == 0) {
                    temp.cnt++;
                    temp.blueC = blueNC;
                    temp.redC = redNC;
                    q.push(temp);
                }
            } 
            // 동
            else {
                node temp = q.front();
                int redNC = temp.redC;
                int blueNC = temp.blueC;
                while (map[temp.redR][redNC + 1] != -1) {
                    if (map[temp.redR][redNC + 1] == 1) {
                        temp.redGoal = 1;
                        break;
                    }
                    redNC++;
                }
                while (map[temp.blueR][blueNC + 1] != -1) {
                    if (map[temp.blueR][blueNC + 1] == 1) {
                        temp.blueGoal = 1;
                        break;
                    }
                    blueNC++;
                }
                if (temp.blueR == temp.redR && redNC == blueNC) {
                    if (temp.redC < temp.blueC) {
                        redNC--;
                    } else {
                        blueNC--;
                    }
                }
                if (temp.blueGoal == 0 && temp.redGoal == 1) {
                    cout << temp.cnt + 1;
                    return 0;
                }
                if (temp.blueGoal == 0 && temp.redGoal == 0) {
                    temp.cnt++;
                    temp.blueC = blueNC;
                    temp.redC = redNC;
                    q.push(temp);
                }
            }
        }
        // 큐에서 제거
        q.pop();
    }

    cout << -1;
    return 0;
}