반응형

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

 

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵의 모든 좌표를 돌면서 주변에 좋아하는 학생 수와 빈칸의 수를 체크하여 자리를 정합니다.

 

2. 좋아하는 학생 수가 같다면 빈 칸의 수가 많은 자리, 빈칸의 수까지 같다면 행의 번호가 낮은 칸, 마지막으로 행의 번호마저 같다면 열의 번호가 낮은 칸에 자리를 정해줍니다.

 

3. 2에서 좋아하는 학생 수도 0, 빈 칸의 수까지 0이라면 제일 처음 나오는 빈자리에 앉아야 하므로 최솟값을 0이 아닌 -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
108
109
110
111
112
113
114
115
116
#include<iostream>
#include<cmath>
 
using namespace std;
 
int N;
int arr[401][4];
int order[401];
int map[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int like(int y, int x, int cur)    //주변 좋아하는 학생 수 체크
{
    int cnt = 0;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
            for (int j = 0; j < 4; j++) {
                if (map[yy][xx] == arr[cur][j]) {
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
int space(int y, int x)        //주변 빈 자리 수 체크
{
    int cnt = 0;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
            for (int j = 0; j < 4; j++) {
                if (map[yy][xx] == 0) {
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
void seat(int cur)    //자리 정하기
{
    int y;
    int x;
    int spaceCnt = -1;    //0이 최솟값이므로 -1로 초기화
    int likeCnt = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] == 0) {    
                int tempLike = like(i, j, cur);
                int tempSpace = space(i, j);
                if (likeCnt < tempLike) {
                    likeCnt = tempLike;
                    spaceCnt = tempSpace;
                    y = i;
                    x = j;
                }
                else if (likeCnt == tempLike) {
                    if (spaceCnt < tempSpace) {
                        spaceCnt = tempSpace;
                        y = i;
                        x = j;
                    }
                }
            }
        }
    }
 
    map[y][x] = cur;
}
 
int ans()    //점수 구하기
{
    int ret = 0;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int cnt = like(i, j, map[i][j]);
            if (cnt > 0) {
                ret += pow(10, cnt - 1);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N * N; i++) {
        int n;
        scanf("%d", &n);
        order[i] = n;
        for (int j = 0; j < 4; j++) {
            scanf("%d", &arr[n][j]);
        }
    }
 
    for (int i = 1; i <= N * N; i++) {
        seat(order[i]);
    }
 
    printf("%d", ans());
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14891번 - 톱니바퀴 (C++)  (0) 2022.09.08
[ 백준 ] 20055번 - 컨베이어 벨트 위의 로봇 (C++)  (0) 2022.09.07
[ 백준 ] 11403번 - 경로 찾기 (C++)  (0) 2022.09.05
[ 백준 ] 17471번 - 게리맨더링 (C++)  (0) 2022.09.04
[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
반응형

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

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 이용하여 인접한 국가 중 인구수 범위에 들어오는 국가들의 인구를 모두 더해주고, 좌표를 vector에 저장해 이동을 하고 이동이 완료되면 ans에 1씩 더해주었습니다. 

 

그러다가 마지막에 이동이 없는 상황이 생기면 ans를 출력해주었습니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
using namespace std;
 
int N, L, R;
int arr[50][50];        //지도
int visited[50][50];    //방문 여부
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<int, int>> pos;
 
void move(int sum)
{
    for (auto next : pos) {    //이동
        int y = next.first;
        int x = next.second;
        arr[y][x] = sum / pos.size();
    }
}
 
int bfs(int y, int x) {        //연합할 국가 찾기
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    int ret = arr[y][x];    //연합할 국가의 총 인구수
    pos.push_back({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
 
                if (diff >= L && diff <= R && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    pos.push_back({ yy,xx });
                    ret += arr[yy][xx];
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d %d", &N, &L, &R);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    int ans = 0;
 
    while (1) {
        bool flag = false;
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] == 0) {
                    pos.clear();
                    int sum = bfs(i, j);
                    move(sum);    //이동
                    if (pos.size() > 1) flag = true;    //이동을 한번이라도 했다면
                }
            }
        }
 
        if (flag == false) {    //이동을 하지 않았다면
            printf("%d", ans);
            return 0;
        }
 
        ans++;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17471번 - 게리맨더링 (C++)  (0) 2022.09.04
[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01
[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
반응형

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

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dfs를 이용하여 궁수의 위치를 정하고, 시뮬레이션을 통해서 죽인 적의 최댓값을 ans에 저장해 출력하였습니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M, D;
int arr[15][15];
int arrow[3];
int ans;
 
int cnt()        //죽인 적의 수
{
    int temp[16][15] = { 0 };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int ret = 0;
 
    while (1) {
        vector<pair<int, int>> die;    //죽일 수 있는 적의 좌표 저장
        for (int k = 0; k < 3; k++) {
            int min = 987654321;
            int y;
            int x;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (temp[j][i] == 1) {
                        if (min > abs(arrow[k] - i) + N - j) {
                            y = j;
                            x = i;
                            min = abs(arrow[k] - i) + N - j;
                        }
                    }
                }
            }
            if (min <= D) {    //거리 안에 있다면 좌표 저장
                die.push_back({ y,x });
            }
        }
        for (auto next : die) {    //좌표가 중복될 수 있으므로 한번에 처리
            if (temp[next.first][next.second] == 1) {
                temp[next.first][next.second] = 0;
                ret++;
            }
        }
        for (int i = N - 1; i >= 0; i--) {    //한칸씩 밀기
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 1) {
                    temp[i + 1][j] = 1;
                    temp[i][j] = 0;
                }
            }
        }
 
        int flag = 0;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 1) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) break;
        }
        if (flag == 0) break;    //적이 하나도 없다면
    }
    return ret;
}
 
void dfs(int level, int num)
{
    if (level == 3) {
        ans = max(cnt(), ans);
        return;
    }
 
    for (int i = num; i < M; i++) {    //궁수의 위치
        arrow[level] = i;
        dfs(level + 1, i + 1);
        arrow[level] = -1;
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &D);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(0, 0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
반응형

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 x가 세로, y가 가로이기 때문에 잘 읽어보고 문제를 푸셔야 합니다.

 

1. 지도와 현재 주사위의 좌표를 입력받습니다.

 

2. 방향에 따라 주사위를 굴려주시고, 주사위의 윗면은 다른 변수에 저장하여 따로 관리해줍니다.

 

3. 바닥이 0이라면 주사위에 있는 숫자를 복사해주고, 아니라면 바닥에 있는 숫자를 주사위에 복사하고 바닥은 0으로 갱신해줍니다.

 

4. 따로 저장해 놓은 윗면의 값을 출력해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M, x, y, K;
int arr[20][20];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int dice[3][3];
int temp1;
int temp2;
 
int main()
{
    scanf("%d %d %d %d %d", &N, &M, &x, &y, &K);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < K; i++) {
        int dir;
        scanf("%d", &dir);
        int yy = y + dy[dir - 1];    //주사위가 움직일 좌표
        int xx = x + dx[dir - 1];
        if (xx >= 0 && xx < N && yy >= 0 && yy < M) {
            if (dir == 1) {    //동쪽
                if (arr[xx][yy] != 0) {
                    dice[1][2] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[1][2];
                }
                temp1 = dice[1][0];
                for (int j = 0; j < 2; j++) {
                    dice[1][j] = dice[1][j + 1];
                }
                dice[1][2] = temp2;
                temp2 = temp1;
            }
            else if (dir == 2) {    //서쪽
                if (arr[xx][yy] != 0) {
                    dice[1][0] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[1][0];
                }
                temp1 = dice[1][2];
                for (int j = 2; j > 0; j--) {
                    dice[1][j] = dice[1][j - 1];
                }
                dice[1][0] = temp2;
                temp2 = temp1;
            }
            else if (dir == 3) {    //북쪽
                if (arr[xx][yy] != 0) {
                    dice[0][1] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[0][1];
                }
                temp1 = dice[2][1];
                for (int j = 2; j > 0; j--) {
                    dice[j][1] = dice[j - 1][1];
                }
                dice[0][1] = temp2;
                temp2 = temp1;
            }
            else {        //남쪽
                if (arr[xx][yy] != 0) {
                    dice[2][1] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[2][1];
                }
                temp1 = dice[0][1];
                for (int j = 0; j < 2; j++) {
                    dice[j][1] = dice[j + 1][1];
                }
                dice[2][1] = temp2;
                temp2 = temp1;
            }
            printf("%d\n", temp2);
            y = yy;
            x = xx;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
반응형

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

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

 

[ 문제풀이 ]

 

덱(deque)이라는 자료구조를 활용하여 문제를 풀었습니다.

 

1. 사과의 위치와 시간에 따른 방향 정보를 입력받습니다.

 

2. 덱을 활용하여 머리와 꼬리의 정보를 저장합니다.

 

3. 사과를 먹으면 꼬리를 그대로 두고, 사과를 먹지 않는다면 꼬리를 덱에서 빼줍니다.

 

4. 벽이나 몸에 부딪히면 현재 시간을 출력해주고 종료합니다.

 

5. 정보를 바탕으로 배열에 값을 저장해줍니다.

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<deque>
 
using namespace std;
 
struct pos {
    int y;
    int x;
};
 
int N, K, L;
int arr[101][101];            //보드
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int dir = 1;
deque<pos> dq;
int cnt;
char direction[10001];        //시간 X이후 움직일 방향 저장할 배열
 
int main()
{
    scanf("%d %d", &N, &K);
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a][b] = 1;
    }
    scanf("%d", &L);
    for (int i = 0; i < L; i++) {
        int a;
        char b;
        scanf("%d %c", &a, &b);
        direction[a] = b;
    }
 
    dq.push_back({ 1,1 });
    arr[1][1] = 2;
 
    while (1)
    {
        int fy = dq.front().y;    //머리
        int fx = dq.front().x;
        int by = dq.back().y;    //꼬리
        int bx = dq.back().x;
 
        int yy = fy + dy[dir];    //이동할 좌표
        int xx = fx + dx[dir];
 
        cnt++;
 
        if (arr[yy][xx] == 2 || yy<1 || yy>N || xx<1 || xx>N) {    //몸통이거나 벽이라면
            printf("%d", cnt);
            return 0;
        }
 
        if (arr[yy][xx] != 1) {    //사과를 먹지 않으면
            arr[by][bx] = 0;
            dq.pop_back();
        }
 
        arr[yy][xx] = 2;
        dq.push_front({ yy,xx });
 
        if (direction[cnt] == 'L') {
            dir--;
        }
        else if (direction[cnt] == 'D') {
            dir++;
        }
 
        if (dir < 0) {
            dir = 3;
        }
        if (dir > 3) {
            dir = 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
반응형

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수를 통해서 벽을 세우고 bfs를 이용하여 바이러스를 퍼뜨린 후 안전 영역의 크기를 구해주면 되는 문제입니다.

 

맵의 최대 크기는 8 X 8 이므로 벽을 세우는데 최대 O(64*63*62)의 시간이 걸리므로 모든 경우의 수를 다 탐색하더라도 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
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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[8][8];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };
int ans;
 
struct pos {
    int y;
    int x;
};
 
int bfs(int map[][8])        //바이러스를 퍼트린 후 안전 영역의 크기를 출력
{
    queue<pos>q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                q.push({ i,j });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] == 0) {
                    map[yy][xx] = 2;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
void dfs(int level, int num)        //벽을 세우기 위한 재귀함수
{
    if (level == 3) {            //벽이 3개라면
        int temp[8][8] = { 0 };
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        int cnt = bfs(temp);
 
        if (ans < cnt) {
            ans = cnt;
        }
 
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (N * i + j > num) {        //이전에 벽을 세운 곳 다음부터 탐색
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    dfs(level + 1, i * N + j);
                    arr[i][j] = 0;
                }
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0, -1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
반응형

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

 

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

queue 두 개를 활용해서 bfs를 돌리면 쉽게 구할 수 있는 문제였습니다.

 

먼저 맵을 입력받을 때 탐색이 좀 더 쉽도록 배열의 1번 인덱스부터 w, h까지 입력을 받습니다. 그 이유는 가장 바깥쪽의 테두리는 자유롭게 다닐 수 있게 하여서 맵에 들어갈 수 있는 입구가 있다면 들어갈 수 있도록 설정하면 0, 0에서 시작하면 되기 때문입니다.

 

 

문을 만나면 키를 가지고 있는지 확인한 다음에 키가 있다면 그냥 열고 지나가고, 없다면 다음에 열쇠가 생겼을 때 열 수 있도록 door이라는 queue에 문의 좌표를 저장해 두었습니다.

 

그리고 키를 만나면 이 키로 열 수 있는 문이 있는지 체크하고 있다면 그 좌표를 q에 집어넣고, 없다면 그냥 지나가는 방법으로 문제를 풀었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
char arr[111][111];            //지도
int visited[111][111];        //방문 여부 체크
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int h, w;
        int key[26] = { 0 };        //몇번 키를 가지고 있는지 체크할 배열
        memset(visited, 0, sizeof(visited));
        memset(arr, 0, sizeof(arr));
        queue<pos> q;
        queue<pos> door[26];        //열쇠가 없는 문에 닿았을 때 좌표 저장
        int cnt = 0;
        cin >> h>> w;
 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> arr[i][j];
            }
        }
 
        string str = "";
        cin >> str;
        if (str != "0") {
            for (int i = 0; i < str.size(); i++) {
                key[str[i] - 'a']++;
            }
        }
 
        q.push({ 0,0 });
        visited[0][0] = 1;
 
        while (!q.empty())
        {
            int y = q.front().y;
            int x = q.front().x;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int yy = y + dy[i];
                int xx = x + dx[i];
                if (yy >= 0 && yy <= h + 1 && xx >= 0 && xx <= w + 1) {
                    if (visited[yy][xx] == 1 || arr[yy][xx] == '*') continue;
                    visited[yy][xx] = 1;
                    
                    if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'Z') {
                        if (key[arr[yy][xx] - 'A'] == 1) {    //열쇠가 있다면 통과
                            q.push({ yy,xx });
                        }
                        else {
                            door[arr[yy][xx] - 'A'].push({ yy,xx });    //없다면 좌표를 저장
                        }
                    }
                    else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'z') {
                        key[arr[yy][xx] - 'a'] = 1;        //키를 가지고 있다고 체크
                        while (!door[arr[yy][xx] - 'a'].empty()) {    //키로 열 수 있는 문 좌표 q에 push
                            int curKey = arr[yy][xx] - 'a';
                            int curY = door[curKey].front().y;
                            int curX = door[curKey].front().x;
                            door[curKey].pop();
                            q.push({ curY,curX });
                        }
                        q.push({ yy,xx });
                    }
                    else if (arr[yy][xx] == '$') {        //문서면 cnt++
                        cnt++;
                        q.push({ yy,xx });
                    }
                    else {
                        q.push({ yy,xx });
                    }
                }
            }
        }
 
        cout << cnt << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
반응형

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

 

2638번: 치즈

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

주어진 모눈종이의 테두리는 치즈가 없다고 하였으므로 0, 0부터 BFS를 돌려 치즈로 둘러싸여 있지 않은 공간들을 2로 초기화시켜주고 치즈들 중 2칸 이상 2에 닿아있는 치즈는 녹이면서 진행하였습니다.

 

그리고 다시 0, 0부터 BFS를 돌려 빈 공간들을 2로 초기화시켜주면서 위의 과정을 반복하고, 치즈가 다 사라지면 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
100
101
102
103
104
105
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int map[100][100];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)        //치즈에 둘러쌓여 있지 않은 공간을 2로 초기화
{
    queue<pos> q;
    memset(visited, 0, sizeof(visited));
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        map[curY][curX] = 2;
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int check()        //치즈가 다 녹았는지 체크하는 함수
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int Cnt(int y, int x)    //실내 온도에 노출 된 횟수를 출력
{
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            if (map[yy][xx] == 2) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
 
    while (!check())        //치즈가 다 녹을 때까지
    {
        bfs(0, 0);        //0, 0부터 2로 빈 공간 2로 초기화
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {    //2칸 이상 닿아있다면 녹임
                    if (Cnt(i, j) >= 2) {
                        map[i][j] = 0;
                    }
                }
            }
        }
 
        cnt++;        //횟수 추가
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
반응형

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

먼저 move 함수를 통해서 공들을 옮겨줍니다. 공을 움직이고 나서 각 공의 좌표를 visited 배열에 저장해서 이전에 똑같은 상황이 있었다면 queue에 넣지 않는 식으로 구현하였습니다.

 

또한, 공을 움직인 횟수가 10회를 초과했다면 continue 하였고, 둘 다 구멍에 들어갔다면 마찬가지로 continue 해주었습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct state {
    int Ry;
    int Rx;
    int By;
    int Bx;
    int cnt;
};
 
int N, M;
char map[10][10];
char temp[10][10];
int visited[10][10][10][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int Ry;
int Rx;
int By;
int Bx;
int ans;
 
void move(int num)                    //구슬을 움직이기 위한 move 함수
{
    for (int i = 1; i < 10; i++) {    //빨간 구슬 옮기기
        int yy = Ry + dy[num] * i;
        int xx = Rx + dx[num] * i;
        if (temp[yy][xx] == 'O') {
            temp[Ry][Rx] = '.';
            Ry = 0;
            Rx = 0;
            break;
        }
        else if (temp[yy][xx] != '.') {
            temp[Ry][Rx] = '.';
            Ry = Ry + dy[num] * (i - 1);
            Rx = Rx + dx[num] * (i - 1);
            temp[Ry][Rx] = 'R';
            break;
        }
    }
 
    for (int i = 1; i < 10; i++) {    //파란 구슬 옮기기
        int yy = By + dy[num] * i;
        int xx = Bx + dx[num] * i;
        if (temp[yy][xx] == 'O') {
            temp[By][Bx] = '.';
            By = 0;
            Bx = 0;
            break;
        }
        else if (temp[yy][xx] != '.') {
            temp[By][Bx] = '.';
            By = By + dy[num] * (i - 1);
            Bx = Bx + dx[num] * (i - 1);
            temp[By][Bx] = 'B';
            break;
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    queue<state> q;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                map[i][j] = '.';
                Ry = i;
                Rx = j;
            }
            else if (map[i][j] == 'B') {
                map[i][j] = '.';
                By = i;
                Bx = j;
            }
        }
    }
 
    q.push({ Ry,Rx,By,Bx,0 });
    visited[Ry][Rx][By][Bx] = 1;
 
    while (!q.empty())
    {
        int curRy = q.front().Ry;
        int curRx = q.front().Rx;
        int curBy = q.front().By;
        int curBx = q.front().Bx;
        int cnt = q.front().cnt;
        q.pop();
 
        if (curRy == 0 && curBy != 0) {        //빨간 구슬만 들어갔을 때 cnt출력
            cout << cnt;
            return 0;
        }
        else if (curRy == 0 && curBy == 0 || cnt >= 10) {
            continue;                        //둘 다 들어갔거나 10번 초과이면 continue
        }
 
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < N; j++) {    //map배열을 temp배열에 복사
                for (int k = 0; k < M; k++) {
                    temp[j][k] = map[j][k];
                }
            }
            Ry = curRy;
            Rx = curRx;
            By = curBy;
            Bx = curBx;
            temp[Ry][Rx] = 'R';                //구슬을 배치
            temp[By][Bx] = 'B';
            for (int j = 0; j < 2; j++) {    //완벽하게 움직이기 위해서 두번 움직임
                move(i);
            }
 
            if (visited[Ry][Rx][By][Bx] != 1) {//이전에 같은 상태가 있었다면 q에 넣지 않기
                visited[Ry][Rx][By][Bx] = 1;
                q.push({ Ry,Rx,By,Bx,cnt + 1 });
            }
        }
    }
 
    cout << -1;        //10번 초과했거나 항상 두 구슬이 다 들어가는 경우
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
반응형

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제의 핵심은 조합을 뽑을 수 있는가 없는가입니다.

 

주어지는 치킨집들 중에서 맥시멈의 치킨집들을 조합으로 모두 뽑아내서 각 치킨집 중 가장 가까운 치킨집들의 거리를 각각 sum에 더해주고 그중 가장 작은 값을 ans에 경신시켜주어서 답을 내면 되는 아주 간단한 방식입니다.

 

처음에는 bfs를 통해서 가장 가까운 치킨집을 구하려고 했었지만 문제에도 나와있듯이 치킨집까지의 거리는 |r1-r2| + |c1-c2|이므로 조합으로 뽑은 모든 치킨집에 대입시켜 가장 가까운 치킨집을 선택하면 됩니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct pos {            //각 좌표를 저장하기 위한 pos struct
    int y;
    int x;
};
 
int N, M;    
int arr[50][50];        //맵
vector<pos> chicken;    //치킨집의 좌표를 저장할 vector
pos box[13];            //조합을 저장할 배역
int sum;
int ans = 987654321;
 
void dfs(int level, int num)
{
    if (level == M)
    {
        sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    int min = 987654321;
                    for (int k = 0; k < M; k++) {
                        int y = box[k].y;        //조합으로 뽑은 치킨집의 좌표를 추출
                        int x = box[k].x;        //거리를 계산 후 dist에 저장
                        int dist = abs(y - i) + abs(x - j);
                        if (min > dist) {        //가장 작은 dist를 min에 저장
                            min = dist;
                        }
                    }
                    sum += min;            //sum에 min을 더함
                }
            }
        }
        if (ans > sum) {            //가장 작은 sum을 ans에 경신
            ans = sum;
        }
        return;
    }
 
    for (int i = num; i < chicken.size()-M+1+level; i++) {
        box[level] = chicken[i];
        dfs(level + 1, i + 1);
        box[level] = { 0,0 };
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];        
            if (arr[i][j] == 2) {    //치킨집들을 chicken vector에 push
                chicken.push_back({ i,j });
            }
        }
    }
 
    dfs(0, 0);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29

+ Recent posts

티스토리툴바