https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

자석들이 회전할 방향을 미리 저장해놓고 풀면 쉽게 풀 수 있는 문제이다.

회전시킬 자석의 왼편과 오른편 자석들을 모두 회전할지 안 할지 검사한다.

회전을 하게 된다면 옆에 있는 자석의 반대방향으로 회전한다.

 

오른편의 자석들을 검사할 때는 순차적으로 왼쪽 자석의 2번 날과 오른쪽 자석의 6번 날을 비교하여

다를 경우에 오른쪽 자석의 회전 방향을 왼쪽 자석의 회전방향의 반대방향으로 저장한다.

마찬가지로 왼편 자석들을 검사할떄도 왼쪽 자석의 2번 날과 오른쪽 자석의 6번 날을 비교하여

회전 방향을 저장한다. 

날의 자성이 같아서 회전하지 않을 경우에는 그 앞의 자석들도 회전하지 않으므로 검사를 중단한다.

 

회전 방향을 모두 저장해줬다면 이제 모든 자석들을 회전시킨다.

1이면 시계방향 -1이면 반시계방향으로 회전시켜준다.

0인 경우(회전하지 않는 경우)도 있으므로 조건 처리를 정확히 해주어야 한다.

 

회전까지 모두 마쳤다면 점수를 계산해준다.

문제에서의 화살표 방향은 각 자석의 0번째 날이므로 자석들의 0번째 날이 S극인지(1 인지) 확인하여 계산해주면 된다.

점수는 각각 1, 2, 4, 8로 2의 제곱수로 더해지므로 << 연산으로 쉽게 더해줄 수 있다.

( 1<< 0 은 1이므로 1점 /  1<<1 은 10(2진수)으로 2점 / 1<<2는 100(2진수)으로 4점 / 1<< 3 은 1000(2진수)으로 8점)

 

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
#include <iostream>
using namespace std;
 
int magnet[4][8];
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        int k;
        cin >> k;
 
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 8; j++) {
                cin >> magnet[i][j];
            }
        }
 
        while (k-- > 0) {
            int num;
            int dir;
            cin >> num >> dir;
            num -= 1;
 
 
            int dirArr[4] = {0,};
            dirArr[num] = dir;
 
 
            //오른쪽 자석 검사
            for (int i = num; i < 3; i++) {
                if (magnet[i][2] != magnet[i+ 1][6]) {
                    dirArr[i + 1] = dirArr[i] * -1;
                }
                else {
                    break;
                }
            }
 
 
            //왼쪽 자석 검사
            for (int i = num; i > 0; i--) {
                if (magnet[i][6] != magnet[i - 1][2]) {
                    dirArr[i - 1] = dirArr[i] * -1;
                }
                else {
                    break;
                }
            }
 
 
            //회전
            for (int i = 0; i < 4; i++) {
 
                //시계방향 회전
                if (dirArr[i] == 1) {
                    int tmp = magnet[i][7];
                    for (int j = 7; j > 0; j--) {
                        magnet[i][j] = magnet[i][j - 1];
                    }
                    magnet[i][0] = tmp;
                }//반시계방향 회전
                else if (dirArr[i] == -1) {
                    int tmp = magnet[i][0];
                    for (int j = 0; j < 7; j++) {
                        magnet[i][j] = magnet[i][j + 1];
                    }
                    magnet[i][7] = tmp;
                }
            }
 
        }
 
 
        //점수 계산
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            if (magnet[i][0] == 1) {
                ans += (1 << i);
            }
        }
 
        cout << '#' << tc << ' ' << ans << '\n';
 
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2019.07.11
[SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호  (0) 2019.07.09
[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스  (0) 2019.07.09

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

출발할 수 있는 모든 칸에서부터 출발하여  대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아온다.

n-1행, n-2행, 0열, n-1열인 곳에서는 사각형을 만들 수 없으므로 출발할 수 없다.

 

각 칸에서 출발하면 오른쪽아래(1,1), 왼쪽 아래(1,-1), 왼쪽 위(-1,-1), 오른쪽 위(-1,1)의 순서로 사각형을 그리도록 했다.

시작점인 경우에만 현재 방향을 유지해서 진행하고 그렇지 않은 경우에는

방향을 꺾어서 이동하는 경우와 현재 방향을 유지한채로 이동하는 경우를 모두 탐색했다.

 

같은 종류의 디저트를 먹으면 안되므로 디저트의 종류를 인덱스로 방문 체크를 해준다.

이동할 곳의 디저트를 아직 먹지 방문하지 않았다면 방문 체크를 해주고 다음 칸으로 이동한다.

이동할 때마다 디저트의 개수를 세주기 위해서  cnt 값을 +1 해서 넘겨준다.

 

이동하다가 이미 방문한 디저트 카페 이지만 그곳이 시작점인 경우에는 출발한 카페로 돌아온 경우이므로

그때까지의 방문한 디저트의 수를 비교해준다.

 
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
#include <iostream>
#include <cstring>
using namespace std;
 
int n, ans;
int sx, sy;
int map[20][20];
int dx[] = {1,1,-1,-1};
int dy[] = { 1,-1,-1,1 };
bool check[101];
 
void solve(int x, int y, int dir, int cnt) {
    
 
    //시작점인 경우
    if (x == sx && y == sy) {
    
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir,cnt+1);
                check[map[nx][ny]] = false;
            }    
        
    }
    else {
 
        
        //현재 방향 유지하는 경우
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir, cnt+1);
                check[map[nx][ny]] = false;
            }
            else if (nx == sx && ny == sy) {
                //방문 표시가 되어있지만 출발점인 경우
                if (ans < cnt) {
                    ans = cnt;
                }
            }
        }
 
 
 
        //방향을 꺾는 경우
        dir += 1;
        if(dir > 3) return;
        nx = x + dx[dir];
        ny = y + dy[dir];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
            if (check[map[nx][ny]] == false) {
                check[map[nx][ny]] = true;
                solve(nx, ny, dir, cnt+1);
                check[map[nx][ny]] = false;
            }
            else if (nx == sx && ny == sy) {
                //방문 표시가 되어있지만 출발점인 경우
                if (ans < cnt) {
                    ans = cnt;
                }
            }
        }
    }
    
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
        ans = -1;
        memset(check, false, sizeof(check));
 
        //시작점
        for (int i = 0; i < n - 2; i++) {
            for (int j = 1; j < n - 1; j++) {
                sx = i;
                sy = j;
                check[map[i][j]] = true;
                solve(sx,sy,0,1);
                check[map[i][j]] = false;
                
            }
        }
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11
[SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호  (0) 2019.07.09
[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스  (0) 2019.07.09

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

 

1987번: 알파벳

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는

www.acmicpc.net

처음 보드를 입력받을 때, 알파벳을 숫자로 변환해서 저장한다.

문자 - 'A'를 해줘서 A는 0, B는 1, C는 2 이런 식으로 저장된다.

 

방문한 알파벳에는 다시 갈 수 없으므로 방문 체크를 해주어야 한다.

A문자를 방문하면 check [0]에 true 체크, B를 방문하면 check [1]을 true 표시해주는 방식으로

방문 체크를 해나간다.

 

인접한 칸으로 이동할 수 있으면 이동할 좌표와 함께 이동 횟수(cnt) 값을 증가시켜서 함께 보내준다.

 

더 이상 갈 수 없는 경우 탐색을 멈추기 위해 z변수를 두고 다음 칸으로 이동할 수 없을 때마다 값을 증가시켜줬다.

z == 4 가 되면(인접한 상하좌우 네 칸으로 모두 갈 수 없으면) 이동한 횟수를 비교해주고 return 한다.

 

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
#include <iostream>
#include <string>
using namespace std;
 
int r, c;
int ans;
bool check[26];
int map[20][20];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int cnt) {
    
 
    int z = 0;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
            z++;
            continue;
        }
        if (check[map[nx][ny]]) {
            z++;
            continue;
        }
 
        
        check[map[nx][ny]] = true;
        solve(nx, ny, cnt+1);
        check[map[nx][ny]] = false;
    }
 
 
    //인접한 칸으로 더이상 이동할 수 없다.
    if (z == 4) {
        if (ans < cnt) ans = cnt;
        return;
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            map[i][j] = s[j] - 'A';
        }
    }
 
 
    check[map[0][0]] = true;
    solve(0,0, 1);
 
 
    cout << ans;
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1182. 부분수열의 합  (0) 2019.07.11
[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 2636. 치즈  (0) 2019.07.08

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

java로 두 번이나 풀어봤던 문제였는데 16진수로 변환하는 부분이 조금 달라서 푸는데 꽤 어려웠다...

 

 

먼저 한칸씩 회전시켜서 만들 수 있는 모든 숫자를 만들어야 하므로 N/4번만큼 돌려준다.

N/4번만큼 돌리면 처음 상태로 돌아오기 때문이다.

 

 

숫자를 구할 때는 먼저 문자들을 숫자로 변환해준다.

문자 0~9는 '0'을 빼줘서 숫자 0~9로 만들어주고

문자 A~F는 'A'를 빼주고(0이 됨) +10을 해주면 16진수 처럼만들어 줄 수 있다.

(ex. 'A' - 'A' + 10 = 10

      'B' - 'A' + 10 = 11)

 

 

모든 문자를 숫자로 만들어 줬으면 이제 각 변에 저장될 숫자를 만들어 준다.

상자는 네 번 이므로 각 변에는 n/4만큼의 숫자가 들어간다.

n/4개의 숫자를 하나의 숫자(16진수)로  만들어주기 위해서 앞자리 수를 16만큼 계속 곱해준다.

한 변의 숫자가 만들어졌으면 벡터에 추가하고 다음 변의 숫자를 만들어준다.

 

 

만들 수 있는 모든 숫자를 벡터에 넣어줬다면

벡터를 정렬하고 중복을 제거해준다.

k 번째로 큰 수를 구해야 하는데 오름차순으로 정렬되므로 

벡터의 size - k를 해주면 바로 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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, k;
string s;
vector<int> num;
 
void getnum() {
    int box[4] = {0,};
    int tmp[28];
 
    //각 문자를 숫자로 변환
    for (int i = 0; i < n; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            tmp[i] = s[i] - '0';
        }
        else { //A~F 는 10~15
            tmp[i] = s[i] - 'A' + 10;
        }
    }
 
 
    //상자의 각 변에 숫자를 넣는다.
    int index = 0;
    //상자의 네 변에 넣어준다.
    for (int i = 0; i < 4; i++) {
        
        //각각의 변에는 n/4개 만큼 들어간다
        for (int j = 0; j < n / 4; j++) {
            //16진수이므로 자릿수가 증가 할때 16을 곱해준다
            box[i] = box[i] * 16 + tmp[index++];
        }
 
        //만들어진 숫자를 벡터에 추가
        num.push_back(box[i]);
    }
 
    
}
 
 
 
void rotate() {
    char tmp = s[n - 1];
    for (int i = n - 1; i > 0; i--) {
        s[i] = s[i - 1];
    }
    s[0] = tmp;
}
 
 
 
void solve() {
    
    // n/4 번째에는 0번째와 같아지므로 n/4번 회전
    for (int i = 0; i < n / 4; i++) {
        //만들 수 있는 숫자들을 구한다.
        getnum();
 
        //회전
        rotate();
    }
    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> k;
        cin >> s;
 
 
        solve();
 
 
        //정렬, 중복 제거
        sort(num.begin(), num.end());
        num.erase(unique(num.begin(), num.end()),num.end());
 
 
        //k번째 큰 수를 출력
        int len = num.size();
        cout << '#'<< tc << ' ' << num[len - k] << '\n';
 
 
        //다음 테스트 케이스를 위해서 벡터 초기화
        num.clear();
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2019.07.11
[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스  (0) 2019.07.09

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

 

이 문제에서 k의 범위는 현재 좌표가 (x, y)라고 했을 때, 

k = |nx-x| + |ny-y|

를 이용해서 k의 범위를 만족하는 (nx, ny)를 구할 수 있다.

 

위의 식을 이용하여 모든 칸에서부터 모든 k의 범위 안에서 집의 수를 구한다.

문제에서 나오는 식을 이용하여 이익을 계산한 후에 손해가 아니라면(이익이 0 이상이라면) 최댓값과 비교한다.

 

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 <iostream>
#include <cmath>
using namespace std;
 
int n, m;
int maxcnt;
int map[20][20];
 
 
void solve(int x, int y) {
    int profit = 0;
 
    //k의 최댓값 n+2 까지 해본다.
    for (int k = 1; k < n+2; k++) {
 
 
        //k범위에 있는 집들을 모두 세준다.
        int homecnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int nx = abs(x - i);
                int ny = abs(y - j);
 
                //k범위 안에 있고 집이 있으면 집의 수 증가
                if (nx + ny < k && map[i][j] == 1) {
                    homecnt++;
                }
            }
        }
 
 
        //이익을 계산
        profit = m*homecnt - (k*k + (k - 1)*(k - 1));
        
        //손해가 아니라면 집의 수를 이전 집의 최대 값과 비교
        if (profit >= 0) {
            if (maxcnt < homecnt) maxcnt = homecnt;
        }
 
    }
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        maxcnt = 0;
        cin >> n >> m;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
 
        //모든 칸에서 시작
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                solve(i, j);
            }
        }
 
        cout <<'#' << tc << ' ' <<  maxcnt << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'SWEA > 모의 SW 역량테스트(C++)' 카테고리의 다른 글

[SWEA] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2019.08.05
[SWEA] 1952. [모의 SW 역량테스트] 수영장  (0) 2019.08.05
[SWEA] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2019.07.11
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2019.07.11
[SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호  (0) 2019.07.09

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

 

7562번: 나이트의 이동

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...

www.acmicpc.net

위의 그림은 체스에서 나이트가 이동할 수 있는 위치를 나타낸다.

시작 위치로부터 도착 위치까지 나이트가 몇 번 움직이면 도착할 수 있는지를 구하는 문제이다.

bfs로 쉽게 최소 이동 횟수를 구해줄 수 있다.

 

 

먼저 시작 위치와 도착 위치가 같은 경우 0을 출력하고 다음 테스트 케이스로 넘어가도록 처리해준다.

그렇지 않다면 bfs로 이동을 시작한다.

현재 좌표에서 나이트가 이동할 좌표를 미리 다음과 같이 만들어 놓는다.

int dx[] = {-2,-2,-1,-1,1,1,2,2};

int dy[] = {-1,1,-2,2,-2,2,-1,1};

 

단계별로 진행하기 위해 큐의 사이즈를 미리 저장해놓고 큐의 사이즈만큼 탐색을 진행한다.

그리고 탐색이 끝날 때마다 count값을 증가시킨다.

도착점에 도착했다면 탐색을 마치고 바로 count값을 출력한다.

 

 

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n;
int sx, sy;
int ex, ey;
bool check[300][300];
 
//나이트가 이동할 수 있는 위치
int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};
 
void bfs() {
    memset(check, false, sizeof(check));
    queue<pair<int, int>> q;
    q.push(make_pair(sx,sy));
    check[sx][sy] = true;
    int count = 0;
 
    while (!q.empty()) {
 
        int qsize = q.size();
 
        while (qsize-- > 0) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int k = 0; k < 8; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (check[nx][ny]) continue;
 
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
        }
 
        count++;
 
        //도착 위치에 도착한 경우 탐색 중단
        if (check[ex][ey]) {
            break;
        }
    }
 
    
    //이동 횟수 출력
    cout << count << '\n';
    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        cin >> sx >> sy;
        cin >> ex >> ey;
        
 
        //시작위치와 도착위치가 같은 경우 0을 출력하고 다음 테스트케이스 진행
        if (sx == ex && sy == ey) {
            cout << 0 << '\n';
            continue;
        }
 
 
        bfs();
    }
 
    
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

www.acmicpc.net

앞에서 풀었던 2636번 치즈 (풀이 링크)문제와 비슷한 문제이다.

다른 점은 4 변 중 2 변 이상이 공기에 접촉해야 치즈가 놓는다.

답도 시간만 출력하면 된다.

 

 

앞의 문제와 마찬가지로 테두리에는 치즈가 없으므로

(0,0)을 먼저 큐에 넣어 바깥 영역을 먼저 bfs로 구하고

치즈가 두번 이상 바깥 영역(공기 부분)과 접촉해있다면 치즈가 녹는다(0이 된다).

 

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
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
 
//치즈수를 카운트
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if (check[nx][ny]) continue;
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            if (board[i][j] == 0) continue;
 
            
            int cnt = 0;
            //네방향을 검사
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (check[nx][ny]) {
                    //공기에 접촉하는 횟수
                    cnt++;
                }
            }
 
 
            //두 변 이상 공기에 접촉하면 녹는다.
            if (cnt >= 2) {
                board[i][j] = 0;
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int time = 0;
    while (true) {
        int tmp = countCheese();
 
        //치즈가 모두 녹으면 break
        if (tmp == 0) {
            break;
        }
    
        solve();
        time++;
    }
 
    cout << time << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06

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

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가

www.acmicpc.net

한 시간마다 공기랑 접촉한 치즈는 녹게 되는데

모든 치즈가 녹아 없어지는 데 걸리는 시간과

한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 구하는 문제다.

 

처음에 바깥 부분과 치즈 가운데 구멍을 어떻게 구분할지 고민하다가

가장자리에는 치즈가 놓여 있지 않는다는 문제 조건을 보고

가장자리부터 시작해서 연결된 영역(치즈가 아닌 바깥 영역)을 구하면 되겠다고 생각했다.

 

처음에 (0,0)부터 큐에 넣고 bfs를 시작하면 바깥공기 영역이 모두 체크된다.

그럼 이제 이 체크된 영역에 인접해 있는 치즈를 없애주면 된다(0으로 만들어 준다).

매시간마다 치즈 수를 세어주고 이전의 치즈수를 저장해둔다.

현재 치즈수가 0이 되면 반복문을 빠져나와  걸린 시간과 이전의 치즈 수 출력해주면 된다.

 

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
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
//치즈수를 센다
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            
            //방문 체크
            if (check[nx][ny]) continue;
            
            //치즈인 경우 skip
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    //바깥영역과 닿아있는 치즈는 녹는다.
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            //치즈 아닌부분 skip
            if (board[i][j] == 0) continue;
 
 
            //상하좌우 중 하나라도 밖이랑 닿아있으면 녹는다.
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (check[nx][ny]) {
                    board[i][j] = 0;
                    break;
                }
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int cheeseCnt= 0;
    int time = 0;
    int lastcnt = 0;
    while (true) {
        int tmp = countCheese();
 
 
        //치즈가 다 녹을 떄까지 반복
        if (tmp == 0) {
            break;
        }
        else {
            lastcnt = tmp;
        }
        
        solve();
        time++;
    }
 
    cout << time << '\n';
    cout << lastcnt << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06
[BOJ] 14889. 스타트와 링크  (0) 2019.07.06

+ Recent posts

티스토리툴바