문제링크

  º  https://www.acmicpc.net/problem/1654

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(2^{31}-1))$

 

풀이

 

k개의 랜선들을 일정한 크기로 잘라서 n개의 랜선으로 만들고 싶은데, 자르는 일정한 크기 중 최대의 크기를 구하는 문제입니다. 랜선의 길이의 범위가 $\mathcal2^{31}-1$ 까지 되서 시간문제 해결을 위해 이분탐색으로 탐색해준다.

탐색을 진행하며 랜선들을 나누어서 개수를 세어준 후 n개 이상이 되는지만 비교하면 되는 간단한 이분탐색입니다.

 

소스코드

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
#include <iostream>
#include <vector>
using namespace std;
int n, k,max_len;
vector <int> v;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> k >> n;
    v.resize(k);
    for (int i = 0; i < k; i++)
    {
        cin >> v[i];
        if (v[i] > max_len)
            max_len = v[i];
    }
    long long ans=0,result,mid,left = 1, right = max_len;
    while (left <= right)
    {
        mid = (left + right) / 2;
        result = 0// 현재 길이로 랜선을 나눴을때의 랜선 개수
        for (int i = 0; i < k; i++)
            result += v[i] / mid;
        if (result >= n) // 랜선 개수가 n개 이상일때 성공
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

 

'Algorithm > boj' 카테고리의 다른 글

백준 11651번 좌표 정렬하기 2  (0) 2021.10.24
백준 13397번 구간 나누기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24

문제링크

  º  https://www.acmicpc.net/problem/11651

 

사용 알고리즘

  º  퀵 소트

 

시간복잡도

  º  $\mathcal{O}(NlogN)$

 

풀이

 

위와 같이 문제에서 제시한 정렬 순서로 sort를 할 수 있게 compare함수를 설계하여 해결하면 되는 정렬문제 입니다.

아래 블로그에서 C++ STL의 사용법을 참고해서 해결하면 됩니다. 언젠가 아래 블로그와 같이 C++ STL에 대한 사용법도 정리할 수 있으면 좋겠습니다. 게을러서 오래걸리겠지만

 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221227975229&proxyReferer=https:%2F%2Fwww.google.com%2F

 

8. C++ STL sort() 함수 다루기 ①

지난 시간까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬의 개념에 대해 이해하고 간단한 프로...

blog.naver.com

소스코드

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <pair<intint>> v;
int n;
bool cmp(pair<intint> a, pair<intint> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < n; i++)
        cout << v[i].first <<' ' <<v[i].second << '\n';
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 1654번 랜선 자르기  (0) 2021.10.24
백준 13397번 구간 나누기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24

문제링크

  º  https://www.acmicpc.net/problem/13397

 

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10000))$

 

풀이

 

N개의 수로 이루어진 배열에서 M개이하의 구간으로 나누어야 하는데, 구간을 나누어야 하는데 나눠진 구간은

구간내의 최댓값 최솟값의 차이를 구간의 점수로 사용합니다. 나누어진 구간들의 점수 중 최댓값을 가장 작게 구간을 나누는 문제입니다.

 

1) 임의의 구간의 점수의 최댓값을 지정하고

2) 그 점수가 사용 가능한지 검사하는 방법으로 해결했습니다.

 

1)은 입력 받은 수 중의 최대값을 right값 최소값인 0을 left값으로 하여 이분탐색을 진행합니다.

$\mathcal{O}(log(10000))$=4의 시간소모. 10000은 입력으로 받을 수 있는 값의 최댓값.

 

2)은 별도의 함수를 만들어 주는데 함수의 로직은 다음과 같습니다.

  (1) n개의 숫자를 for문으로 탐색하며 매 index에서 최솟값과 최댓값을 계속 갱신해줍니다.

  (2) 그 후 현 위치의 (최댓값-최솟값)≤검사할 구간의 점수 가 성립하는지 검사를 합니다.

     if 성립하지 않다면 구간의 개수를 하나 추가 그리고 현재 index의 수를 최솟값 최댓값으로 만들어주고 다음 indxe의 검사를 해줍니다.

  (3) 검사해서 나온 구간의 개수가 m보다 작거나 같다면 검사결과를 true, 아니라면 false로 출력해줍니다.

$\mathcal{O}(log(N)$의 시간소모.

 

소스코드

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
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector <int> v;
bool check(int mid)
{
    int max_num=-1,min_num=10001, cnt = 1;
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            min_num = v[i];
            max_num = v[i];
        }
        if (v[i] < min_num) // 최솟값 갱신
            min_num = v[i];
        if (v[i] > max_num) // 최댓값 갱신
            max_num = v[i];
        if (max_num - min_num > mid) // 구간의 점수가 넘어가면
        {
            cnt += 1// 새로운 구간 시작
            max_num = v[i];
            min_num = v[i];
        }
    }
    if (m >= cnt)
        return true;
    else
        return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    v.resize(n);
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }
    int ans=1987654321,mid, left = 0, right = sum;
    while (left <= right) // // 구간의 점수값 이분탐색
    {
        mid = (left + right) / 2
        if (check(mid))
        {
            right = mid - 1;
            if (mid < ans)
                ans = mid;
        }
        else
            left = mid + 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 1654번 랜선 자르기  (0) 2021.10.24
백준 11651번 좌표 정렬하기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24

문제링크

  º  https://www.acmicpc.net/problem/1939

 

사용 알고리즘

  º  BFS, 이분탐색

 

시간복잡도

  º  $\mathcal{O}(NlogC)$  N(2≤N≤10,000), M(1≤M≤100,000), C(1≤C≤1,000,000,000)

 

풀이

 

섬들 간 사이를 잇는 다리의 정보와 다리의 중량 제한들이 입력으로 주어질 때, 시작섬과 도착섬을 오갈 수 있는 물품들의 최대 중량값을 구하는 문제입니다. 중량값을 기준으로 탐색을 진행하여 그 중량으로 이동이 가능한지 검사를 해주면 해결할 수 있는 문제였습니다.

 

1.  이분탐색을 사용하여 최소무게 1부터 입력 받은 최대무게 사이를 이분탐색하여 현재 물품들의 중량(cost)이 시작섬에서 도착섬까지 이동가는한지 검사합니다. 최대 무게는 10억이므로  $\mathcal{O}(log10^10)$ = 10의 시간소모.

 

2. BFS또는 DFS로 그래프를 설정한 무게(cost)로 탐색해줍니다. $\mathcal{O}(10000+100000)$ = 110000의 시간소모.

 

소스코드

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, max_cost, st, ed;
vector <pair<intint>> v[10001];
bool bfs(int cost)
{
    vector <bool> check(n + 1); // 방문을 표시할 bool 배열
    check[st] = true;
    queue <int> q;
    q.push(st);
    int cur, next, next_cost;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        if (cur == ed) // 도착섬에 도착
            return true;
        for (int i = 0; i < v[cur].size(); i++)
        {
            next = v[cur][i].first;
            next_cost = v[cur][i].second;
            if (check[next] == false && cost <= next_cost) // 방문한적없고 물품들의 무게가 다음섬의 제한보다 작으면 이동가능
            {
                check[next] = true;
                q.push({ next });
            }
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
        if (c > max_cost)
            max_cost = c;
    }
    cin >> st >> ed;
    int ans = 0, mid, left = 1, right = max_cost; // 무게의 최소값은 1, 최대값은 제한의 최대 무게
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (bfs(mid)) // 현재 중량의 물품들로 공장간의 이동을 할 수 있는지 bfs탐색으로 검사
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 11651번 좌표 정렬하기 2  (0) 2021.10.24
백준 13397번 구간 나누기 2  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11

문제링크

  º  https://www.acmicpc.net/problem/2805

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10^{10}))$

 

풀이

 

N개의 나무들이 주어질때 상근이가 나무를 M미터 챙겨서 가려고 합니다. 나무를 절단하는 높이가 H라고 할때 H보다 높은 부분 즉 나무의 높이 - H만큼의 길이가 한 나무에서 자르는 나무의 길이일때 이걸 합쳐서 M미터를 만들어주면 됩니다.

문제해결을 위해선 H의 높이를 계속해서 주어진 입력값에 대해 적용하여 잘라줘야하는데 나무의 높이로 주어질 수 있는 최대값이 10억입니다. 그래서 이분탐색으로 자를 나무의 높이를 탐색합니다. 최대 $\mathcal{O}(log(10^{10}))$ = 10d의 시간소모.

 탐색을 진행하며 동시에 나무를 잘라서 M미터가 되는지 검사해주는데 지금 자르는 높이보다 작은 나무는 자른 높이를 더해주면 안됩니다. (당연한 얘기같지만 저는 그래서 답이 다르게 나오길래 뭐지했습니다.) 어찌됐든 그래서 M미터 이상이고 지금 정답으로 설정한 높이보다 높으면 갱신해줍니다. 최댓값을 찾아야하니까.

 

소스코드

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
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n;
    long long m,max_t=0;
    vector <long long> v;
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        if (v[i] > max_t)
            max_t = v[i]; // 가장 큰 키의 나무를 찾아준다.
    }
    long long mid,left = 0, right = max_t, result, ans = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        result = 0;
        for (int i = 0; i < n; i++)
        {
            if(mid <v[i]) // 자르는 길이보다 나무가 클때만 잘라준다.
                result += (v[i] - mid);
        }
        if (result >= m)
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 13397번 구간 나누기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11

문제링크

  º  https://www.acmicpc.net/problem/2110

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10^{10}))$

 

풀이

 

문제에서의 설명이 애매하게 느껴지는데 공유기를 설치한다는 의미는 연속하는 점들을 묶어주는 것과 같은 의미라고 보면 됩니다. 즉, 그룹을 만들어주는 것인데 그룹간의 간격의 최대길이를 지정해 놓고 그 간격으로 최대한의 그룹을 만들어서 묶어주면 그룹이 C개 이상이면 문제를 해결할 수 있습니다.

 

최대길이를 시작점과 끝점의 거리차로 해서 이분탐색을 시작하여 매 탐색시 그룹간격 최대길이로 그룹을 만들어주는 로직을 해줍니다.

그 로직은 전 점의 좌표와 현 점의 좌표의 거리차를 그룹간격 최대길이를 mid라 할때 mid 이상인지 검사해줍니다. mid미만의 값이면 한 공유기에 넣어도 최대길이를 초과할 일이 없기 같은 공유기에 넣어주고, 아니면 새 그룹으로 시작해줍니다.

따라서 탐색은 최대로 나올 수 있는 좌표 10억과 1의 차이인 $\mathcal{O}(log(10^{10}))$=10

매 탐색시 $\mathcal{O}(N)$의 시간소모. 최종적으로 둘을 곱해줍니다.

 

소스코드

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n,c;
    vector <long long> v;
    cin >> n >> c;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int prev,result,ans=0,mid, left = 1, right = v[n - 1]-v[0]; // 오른쪽 최대범위 시작점과 끝점의 거리차
    while (left <= right)
    {
        mid = (left + right) / 2;
        result = 1;
        prev = v[0];
        for (int i = 1; i < n; i++)
        {
            if (v[i] - prev >= mid) // 현재 설정한 최대거리 이상이면 공유기를 하나더추가해줌
            {
                result += 1;
                prev = v[i];
            }
        }
        if (result >= c) // 공유기 개수가 C이상이면 정답보다 큰지 비교
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

 

'Algorithm > boj' 카테고리의 다른 글

백준 1939번 중량제한  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 14503 로봇 청소기  (0) 2019.11.11
백준 15662번 톱니바퀴 (2)  (0) 2019.11.10

문제 링크

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

알고리즘 분류

 

시뮬레이션

 

풀이

 

문제의 조건에 맞게 경사로를 설치해주는 시뮬레이션 문제입니다.

고려해야할 조건은 다음과 같습니다.

 

1. 경사로를 설치하는 곳의 낮은칸과 높은칸의 높이차는 1이어야 합니다.

2. L개의 블록이 연속되어야 합니다.

3. 경사로가 이미 설치된 곳은 경사로를 설치 할 수 없습니다.

 

이러한 조건을 행과 열을 검사하는 함수를 따로 만들어서 문제를 해결했습니다.

 

코드

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
#include <iostream>
 
using namespace std;
 
int n, l,ans;
int map[101][101];
bool check[101][101];
 
void checky(int cur) // 행 검사
{
    for (int i = 0; i < n - 1; i++)
    {
        if (map[cur][i] != map[cur][i + 1]) // 높이가 다르면 경사로 건설
        {
            if (map[cur][i] > map[cur][i + 1]) // 현재 블록보다 높이가 낮을 경우
            {
                if (map[cur][i] - map[cur][i + 1== 1// 높이 차이가 1일 경우
                {
                    for (int j = i + 1; j < i + 1 + l; j++)
                    {
                        if (map[cur][i + 1== map[cur][j] && !check[cur][j]) // 경사로가 없고 높이가 같아야함
                        {
                            check[cur][j] = true// 경사로 설치
                        }
                        else
                            return;
                    }
                }
                else
                    return;+
            }
            else // 현재 블록 보다 높이가 높을 경우
            {
                if (map[cur][i + 1- map[cur][i] == 1// 높이 차이가 1일 경우
                {
                    for (int j = i; j > i - l; j--)
                    {
                        if (map[cur][i] == map[cur][j] && !check[cur][j]) // 경사로가 없고 높이가 같아야함
                        {
                            check[cur][j] = true// 경사로 설치
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
        }
    }
 
    ans++;
}
 
void checkx(int cur) // 열검사
{
    for (int i = 0; i < n - 1; i++)
    {
        if (map[i][cur] != map[i+1][cur])
        {
            if (map[i][cur] > map[i+1][cur])
            {
                if (map[i][cur] - map[i+1][cur] == 1)
                {
                    for (int j = i + 1; j < i + 1 + l; j++)
                    {
                        if (map[i+1][cur] == map[j][cur] && !check[j][cur])
                        {
                            check[j][cur] = true;
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
            else
            {
                if (map[i+1][cur] - map[i][cur] == 1)
                {
                    for (int j = i; j > i - l; j--)
                    {
                        if (map[i][cur] == map[j][cur] && !check[j][cur])
                        {
                            check[j][cur] = true;
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
        }
    }
    
    ans++;
}
int function()
{
    freopen("input.txt""r", stdin);
    setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> l;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    ans = 0;
    for (int i = 0; i < n; i++)
    {
        checky(i);
    }
    memset(check, 0sizeof(check));
    for (int i = 0; i < n; i++)
    {
        checkx(i);
    }
 
    printf("%d\n", ans);
    
 
    return 0;
}

'Algorithm > boj' 카테고리의 다른 글

백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24
백준 14503 로봇 청소기  (0) 2019.11.11
백준 15662번 톱니바퀴 (2)  (0) 2019.11.10
백준 14891번 톱니바퀴  (0) 2019.11.10

문제 링크

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음

www.acmicpc.net

 

문제 유형

 

시뮬레이션

 

풀이

 

문제의 조건대로 구현해주면 되는 시뮬레이션 문제입니다.

청소한 곳은 map의 값을 2, 청소가 안된 빈 곳은 0, 벽은 1로 표현했습니다.

1. 현재 위치를 청소해준다.

2. 네 방향 모두 청소가 되어있거나 벽인 경우

 2-1. 현재 방향의 뒤의 블록이 벽인 경우 종료

 2-2. 벽이 아닌 경우 뒤로 후진

3. 네 방향 중 청소가 안되었거나 벽이 아닌 경우(회전해준 후)

 3-1. 왼쪽 방향이 청소가 안되었다면 앞으로 전진

 3-2. 왼쪽 방향이 청소가 되었다면 회전만 한다.

위의 문제의 조건을 구현해주면 되는 간단한 문제였습니다.

 

소스 코드

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
#include <iostream>
 
using namespace std;
 
int n, m, y, x,d;
int map[51][51];
int dy[4= { -1,0,1,0 };
int dx[4= { 01,0,-1 };
 
int function()
{
    freopen("input.txt""r", stdin);
    setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> y >> x >> d;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
 
    int ans = 0;
 
    while (1)
    {
        if (map[y][x] == 0
            ans++;
        map[y][x] = 2;
 
        if (map[y][x - 1!= 0 && map[y][x + 1!= 0 && map[y - 1][x] != 0 && map[y + 1][x] != 0)     
        {// 네 방향 모두 청소되었거나 벽
            if (map[y - dy[d]][x - dx[d]] != 1// 뒤쪽에 벽이 아니라 후진
            {
                y -= dy[d];
                x -= dx[d];
            }
            else // 후진 못할 시
            {
                break;
            }
        }
        else
        {
            if (d == 0)
                d = 3;
            else
                d -= 1;
            
            if (map[y + dy[d]][x + dx[d]] == 0// 회전한방향이 청소안한 칸
            {
                y += dy[d];
                x += dx[d];
            }
            //else 청소한칸이거나 벽
        }
    }
 
    cout << ans;
 
    return 0;
}

'Algorithm > boj' 카테고리의 다른 글

백준 2110번 공유기 설치  (1) 2021.10.24
백준 14890번 경사로  (0) 2019.11.11
백준 15662번 톱니바퀴 (2)  (0) 2019.11.10
백준 14891번 톱니바퀴  (0) 2019.11.10
백준 14499번 주사위 굴리기  (0) 2019.11.10

+ Recent posts