반응형

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

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. queue를 만들어 카드를 뽑고 다시 넣는 행동을 반복하다가 queue의 사이즈가 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
 
    queue<int> q;
 
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }
 
    while (q.size() != 1) {
        q.pop();
        int temp = q.front();
        q.pop();
        q.push(temp);
    }
 
    cout << q.front();
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5022번 - 연결 (C++)  (1) 2023.06.19
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
[ 백준 ] 14497번 - 주난의 난(難) (C++)  (0) 2023.06.16
[ 백준 ] 10464번 - XOR (C++)  (0) 2023.06.15
[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
반응형

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

 

1175번: 배달

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ N ][ M ][ dir ][ del ] 배열을 만들어서 위치, 방향, 배달 여부를 저장합니다.

 

2. 지도에서 S의 위치를 queue에 넣고, '.'로 초기화합니다.

 

3. 지도에서 C의 위치를 '0', '1'로 초기화합니다.

 

4. bfs를 통해 배달을 하고, 숫자를 만나면 del | (1 << arr [ yy ][ xx ] - '0')를 통해 배달 여부를 초기화합니다.

 

5. 배달을 완료했을 때 cnt를 출력합니다.

 

6. 배달이 불가능할 때 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int visited[50][50][4][4];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
char arr[51][51];
 
struct node {
    int y;
    int x;
    int dir;
    int del;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
    queue<node> q;
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 'S') {
                q.push({ i,j,-1,0,0 });
                visited[i][j][0][0] = 1;
                visited[i][j][1][0] = 1;
                visited[i][j][2][0] = 1;
                visited[i][j][3][0] = 1;
                arr[i][j] = '.';
            }
            if (arr[i][j] == 'C') {
                arr[i][j] = '0' + cnt++;
            }
        }
    }
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int dir = q.front().dir;
        const int del = q.front().del;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (del == 3) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            if (i != dir) {
                const int yy = y + dy[i];
                const int xx = x + dx[i];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                    if (arr[yy][xx] == '.' && visited[yy][xx][i][del] == 0) {
                        visited[yy][xx][i][del] = 1;
                        q.push({ yy,xx,i,del,cnt + 1 });
                    }
                    else if (arr[yy][xx] >= '0' && arr[yy][xx] < '2') {
                        const int temp = del | (1 << arr[yy][xx] - '0');
                        if (visited[yy][xx][i][temp] == 0) {
                            visited[yy][xx][i][temp] = 1;
                            q.push({ yy,xx,i,temp,cnt + 1});
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27

+ Recent posts

티스토리툴바