티스토리 뷰

 

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

 

17071번: 숨바꼭질 5

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

진짜 어려웠다. 한 2~3일? 고민했는데도 어려워서 질문 게시판 보고 힌트를 얻어서 풀었다.

엄청 깔끔하게 짠 코드는 아니지만 내 블로그 기록의 목적은 공부용이니까 우선 남겨둔다.

 

처음 내가 생각했던 방법은 다음과 같았다.

1. 수빈이를 BFS할 배열 subin과 동생을 BFS할 배열 brother를 각각 만들어서, 수빈이 1초, 동생 1초 이렇게 진행한다. 이 때 동생의 현재 위치 k는 따로 저장해둔다.

2. subin[k]와 brother[k]가 0이 아니면서(초기값이 0이므로) 둘 다 동일한 값이 들어가면 리턴하고 종료한다.

 

이렇게 생각해서 풀수 있을줄 알았는데, 예제 2번이 복병이었다.

예제 2번의 수빈이의 이동 순서는 17-18-17-16-15, 동생은 5-6-8-11-15였는데, BFS는 동일한 위치에 한 번만 방문하는게 조건이였기 때문이다.(이 조건을 어기고 여러 번 방문하면 큐에 너무 많은 원소가 들어와서 메모리 초과로 터진다)

이를 해결하기 위해서 다양한 방법을 써보다가 17-18-17은 0초,2초고 이는 같은 짝수나 홀수일 때라면 정답을 출력할 수 있겠구나 싶은 생각이 들었는데, 또 18 66이 문제더라.

18 66은 76에서 만나야 하는데, 수빈과 동생으로 나누니까 수빈이는 72에서 2초일때 값이 저장되고, 동생은 72가 3초일때 값이 저장되더라. 

여기서 막혀서 좀 찾아보니까 짝수/홀수로 아예 나누는 방법이 있다는걸 알게 되었고, subin 배열을 odd,even으로 나누어서 저장해서 맞췄다.

 

결국 내가 풀었던 방법은 다음과 같았다.

1. 수빈이를 짝수/홀수로 나눠서 저장할 배열 odd,even과 동생을 BFS할 배열 brother를 만들어서, 수빈이 1초씩, 동생 1초씩 진행한다. 이때 동생의 현재 위치 k와 BFS를 진행한 시간 ksec는 따로 저장해둔다.

2. ksec가 홀수이고 odd[k]와 brother[k]에 값이 있거나 / ksec가 짝수이고 even[k]와 brother[k]에 값이 있으면 brother[k]를 리턴한다.

 

brother[k]를 리턴하는 이유는 간단하게 수빈이가 도착한 시간이 아닌 동생이 도착한 시간을 리턴해야 하기 때문이다.

 

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
#include <iostream>
#include <queue>
using namespace std;
#define MAX 500002
queue <pair<intint>> q, sub;
int odd[MAX], even[MAX], brother[MAX];
bool vis[MAX];
int n, k, ksec;
void input()
{
    cin >> n >> k;
}
int solve()
{
    q.push({ n,0 });
    sub.push({ k,0 });
    if (n == k)
    {
        if (n > 500000return -1;
        return 0;
    }
    while (!q.empty() || !sub.empty())
    {
        if (k > 500000return -1;
 
        if (ksec % 2 == 0 && even[k] != 0 && brother[k] != 0// 현재 이동한 시간이 짝수
        {
            return brother[k];
        }
        else if (ksec % 2 == 1 && odd[k] != 0 && brother[k] != 0// 현재 이동한 시간이 홀수
        {
 
            return brother[k];
        }
        
        int t = q.size(); 
        while (t--// 수빈 짝수/홀수로 나누기
        {
            auto cur = q.front(); q.pop();
            int x, sec;
            x = cur.first; sec = cur.second;
            sec++// 여기서 1 증가시켜주는 이유는 if문장의 조건을 만족하기 위해서
                    
            if (sec % 2 == 1// 위에서 증가시켜야 1초일때 홀수, 2초일때 짝수... 배열로 들어감
 
            {
                if (x > 0 && odd[x - 1== 0)
                {
                    odd[x - 1= sec;
                    q.push({ x - 1,sec });
 
                }
                if (x < 500000 && odd[x + 1== 0)
                {
                    odd[x + 1= sec;
                    q.push({ x + 1,sec });
                }
                if (x > 0 && x * 2 <= 500000 && odd[x * 2== 0)
                {
                    odd[x * 2= sec;
                    q.push({ x * 2,sec });
                }
            }
            else
            {
                if (x > 0 && even[x - 1== 0)
                {
                    even[x - 1= sec;
                    q.push({ x - 1,sec });
 
                }
                if (x < 500000 && even[x + 1== 0)
                {
                    even[x + 1= sec;
                    q.push({ x + 1,sec });
                }
                if (x > 0 && x * 2 <= 500000 && even[x * 2== 0)
                {
                    even[x * 2= sec;
                    q.push({ x * 2,sec });
                }
            }
 
        }
 
        t = sub.size();
        while (t--// 동생 x+sec초 증가
        {
 
            auto cur = sub.front(); sub.pop();
            int x, sec;
            x = cur.first; sec = cur.second;
            if (brother[x + ++sec] == 0)
            {
                brother[x + sec] = sec;
                sub.push({ x + sec,sec });
                k = x + sec;
                ksec = sec;
            }
 
        }
 
 
 
    }
    return -1;
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    input(); cout << solve();
}
cs

여담인데, 처음 푼 플래문제라 엄청 뿌듯했다.

 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
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
글 보관함