백준 문제풀이/GOLD

[백준 / BOJ / GOLD 4] 3055 번 : 탈출

2020. 4. 1. 22:50
반응형

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

 

3055번: 탈출

문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나

www.acmicpc.net

문제 접근법

  • 단순 이동만이 아니라 물이 매턴마다 차오르는것을 신경써야 하는 문제이다.
  • 주어진 맵을 그리기 위한 2차원 배열 1개와 물이 차오르는 맵을 그릴 2차원 배열 1개를 준비한다.
  • 물이 차오르는 맵을 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
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
#include<cstdio>
#include<queue>
 
using namespace std;
 
int waterMap[51][51];
char escapeMap[51][51];
bool visit[51][51];
bool check;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0};
 
int main()
{
    int r, c;
    queue<pair<pair<int, int>, int>> q;
    queue<pair<int, int>> q1;
 
    scanf("%d %d", &r, &c);
 
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            scanf(" %c", &escapeMap[i][j]);
            waterMap[i][j] = 9999;
 
            if (escapeMap[i][j] == 'S')
            {
                q.push(make_pair(make_pair(i, j), 0));
            }
            else if (escapeMap[i][j] == '*')
            {
                q1.push(make_pair(i, j));
                waterMap[i][j] = 0;
            }
        }
    }
 
    while (!q1.empty())
    {
        int x = q1.front().first;
        int y = q1.front().second;
        q1.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 1 || nx > r || ny < 1 || ny > c || escapeMap[nx][ny] == 'D' || escapeMap[nx][ny] == 'X') continue;
 
            if (escapeMap[nx][ny] == '.' && waterMap[nx][ny] - 1 > waterMap[x][y])
            {
                waterMap[nx][ny] = waterMap[x][y] + 1;
                q1.push(make_pair(nx, ny));
            }
        }
    }
 
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int moveCount = q.front().second;
        visit[x][y] = true;
 
        q.pop();
 
        if (escapeMap[x][y] == 'D')
        {
            printf("%d", moveCount);
            check = true;
            break;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 1 || nx > r || ny < 1 || ny > c || escapeMap[nx][ny] == 'X') continue;
 
            if ((escapeMap[nx][ny] == 'D' || escapeMap[nx][ny] == '.') && moveCount < waterMap[nx][ny] - 1 && !visit[nx][ny])
            {
                visit[nx][ny] = true;
                q.push(make_pair(make_pair(nx, ny), moveCount + 1));
            }
        }
    }
 
    if (!check)
    {
        printf("%s", "KAKTUS");
    }
 
    return 0;
}
Colored by Color Scripter
 
반응형

'백준 문제풀이 > GOLD' 카테고리의 다른 글

[백준 / BOJ / GOLD 5] 16234 번 : 인구 이동  (0) 2021.03.22
[백준 / BOJ / GOLD 5] 9019 번 : DSLR  (0) 2020.04.10
[백준 / BOJ / GOLD 4] 13913 번 : 숨바꼭질 4  (0) 2020.03.28
[백준 / BOJ / GOLD 5] 13549 번 : 숨바꼭질 3  (0) 2020.03.27
[백준 / BOJ / GOLD 3] 10942 번 : 팰린드롬?  (0) 2020.03.21
'백준 문제풀이/GOLD' 카테고리의 다른 글
  • [백준 / BOJ / GOLD 5] 16234 번 : 인구 이동
  • [백준 / BOJ / GOLD 5] 9019 번 : DSLR
  • [백준 / BOJ / GOLD 4] 13913 번 : 숨바꼭질 4
  • [백준 / BOJ / GOLD 5] 13549 번 : 숨바꼭질 3
지나가던 개발자
지나가던 개발자
지나가던 개발자
나의 발전을 위한 공간
지나가던 개발자
전체
오늘
어제
  • 분류 전체보기 (221)
    • 언어 (86)
      • C++ (43)
      • JAVA (43)
    • 게임 개발 (4)
      • 간단한 RPG 게임 만들기 (4)
      • 게임 개발 이슈 해결 (0)
    • 백준 문제풀이 (36)
      • PLATINUM (0)
      • GOLD (13)
      • SILVER (21)
      • BRONZE (2)
    • 프로그래머스 문제풀이 (32)
      • LEVEL 5 (0)
      • LEVEL 4 (0)
      • LEVEL 3 (7)
      • LEVEL 2 (19)
      • LEVEL 1 (6)
    • SQL 문제풀이 (15)
      • 프로그래머스 (4)
      • 해커랭크 (11)
    • 디자인 패턴 (1)
    • 웹 (17)
      • 웹 이론 정리 (17)
    • CS 지식 (28)
      • 알고리즘 (0)
      • 데이터베이스 (11)
      • 자료구조 (0)
      • 네트워크 (7)
      • 그래픽스 (0)
      • 운영체제 (9)
      • 기타 (1)
    • Git (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 깃 허브

공지사항

인기 글

태그

  • 해커랭크
  • Level 2
  • 상속
  • 객체 지향 설계
  • 클래스와 인터페이스
  • 객체 생성과 파괴
  • mysql
  • Silver 3
  • 백준
  • 프로그래머스
  • 설계 및 선언
  • level 1
  • 열거 타입과 애너테이션
  • 소멸자 및 대입 연산자
  • Chapter 6
  • Gold 5
  • BOJ
  • Chapter 4
  • java
  • c++

최근 댓글

최근 글

hELLO · Designed By 정상우.
지나가던 개발자
[백준 / BOJ / GOLD 4] 3055 번 : 탈출
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.