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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 100X100 맵을 입력받는다.

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
#include <iostream>
#include <algorithm>
using namespace std;
 
const int MAX = 100;
 
int map[MAX][MAX];
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        int case_num;
        cin >> case_num;
 
        //맵 입력
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                cin >> map[i][j];
            }
        }
 
        //최댓값 찾기
        int res = 0;
 
        //sumA : 행의 합, sumB : 열의 합, sumC : 좌샹향 대각선의 합, sumD : 우상향 대각선의 합
        int sumC = 0, sumD = 0;
        for (int i = 0; i < MAX; i++) {
            int sumA = 0, sumB = 0;
            sumC = map[i][i];
            sumD = map[i][99 - i];
            for (int j = 0; j < MAX; j++) {
                sumA += map[i][j];
                sumB += map[j][i];
            }
            res = max(max(sumA, sumB), res);
        }
        res = max(max(sumC, sumD), res);
 
        //출력
        cout << "#" << case_num << " " << res << "\n";
    }
}
 

 

2차원 배열에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1238 - Contact  (0) 2020.05.03
[C++] SWEA 1219 - 길찾기  (0) 2020.05.03
[C++] SWEA 1954 - 달팽이 숫자  (0) 2020.05.03
[C++] SWEA 1974 - 스도쿠 검증  (0) 2020.05.03
[C++] SWEA 1953 - 탈주범 검거  (0) 2020.05.03

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 숫자 N을 입력 받고, N*N 배열을 만든다.

2. 배열에 시작부터 끝까지 순서에 맞게 1부터 N*N을 채워넣는다.

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
#include <iostream>
#include <cstring>
using namespace std;
 
struct snail {
    //좌표
    int x, y;
    //방향
    int dir;
    //숫자
    int num;
};
 
//동,남,서,북
int di[] = { 0,1,0,-1 };
int dj[] = { 1,0,-1,0 };
 
int N;
int map[12][12];
 
void go(snail cur) {
 
    //종료조건 : 숫자를 다 채웠을 경우
    if (cur.num > N * N) {
        return;
    }
 
    map[cur.x][cur.y] = cur.num;
    
    //다음 갈 곳
    snail nxt;
    nxt.x = cur.x + di[cur.dir];
    nxt.y = cur.y + dj[cur.dir];
    nxt.dir = cur.dir;
    nxt.num = cur.num + 1;
 
    //다음 갈 곳이 범위를 넘었거나 이미 숫자가 채워져있는 경우, 다음 방향으로 전환
    if (nxt.x <= 0 || nxt.y <= 0 || nxt.x > N || nxt.y > N || map[nxt.x][nxt.y] > 0) {
        nxt.dir++;
        if (nxt.dir == 4) {
            nxt.dir = 0;
        }
 
        nxt.x = cur.x + di[nxt.dir];
        nxt.y = cur.y + dj[nxt.dir];
    }
 
    go(nxt);
 
    return;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        cin >> N;
 
        memset(map, 0, sizeof(map));
 
        //(1,1)에서 0방향(동)으로 숫자 1로 시작
        //범위를 넘어가는 것과 숫자가 채워진 예외 경우를 한꺼번에 처리하기 위해 1,1부터 시작
        snail start = { 1,1,0,1 };
        go(start);
 
        cout << "#" << test_case << "\n";
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cout << map[i][j] << " ";
            }
            cout << "\n";
        }
    }
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1238 - Contact  (0) 2020.05.03
[C++] SWEA 1219 - 길찾기  (0) 2020.05.03
[C++] SWEA 1209 - Sum  (0) 2020.05.03
[C++] SWEA 1974 - 스도쿠 검증  (0) 2020.05.03
[C++] SWEA 1953 - 탈주범 검거  (0) 2020.05.03

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 스도쿠 9X9 퍼즐을 입력 받는다.

2. 스도쿠 퍼즐의 각 행,열,칸에 1~9숫자의 유무를 저장하는 배열을 생성한다.

3. 숫자가 모두 있는지 없는지 판단하여 출력한다.

​

<해법>

1. 스도쿠 퍼즐의 각 행,열,칸에 1~9숫자의 유무를 저장하는 배열

=> 맵 입력과 동시에 이루어진다. 아래 사진과 코드를 참고하시면 됩니다.

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
#include <iostream>
#include <cstring>
using namespace std;
 
int map[10][10];
//각각의 행,열,3X3칸에 대해 1~9숫자가 있는지 판별
bool check[3][10][10];
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        memset(check, false, sizeof(check));
 
        //입력
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                cin >> map[i][j];
 
                //i행에 입력된 숫자(map[i][j]) = true
                check[0][i][map[i][j]] = true;
                //j열에 입력된 숫자 = true
                check[1][j][map[i][j]] = true;
                
                //3X3칸에 입력된 숫자 = true
                int index = ((i - 1) / 3 * 3) + 1 + (j - 1) / 3;
                check[2][index][map[i][j]] = true;
            }
        }
 
        //check배열이 모두 true로 되어있는지 확인
        int res = 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j <= 9; j++) {
                for (int k = 1; k <= 9; k++) {
                    if (!check[i][j][k]) {
                        res = 0;
                    }
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1238 - Contact  (0) 2020.05.03
[C++] SWEA 1219 - 길찾기  (0) 2020.05.03
[C++] SWEA 1209 - Sum  (0) 2020.05.03
[C++] SWEA 1954 - 달팽이 숫자  (0) 2020.05.03
[C++] SWEA 1953 - 탈주범 검거  (0) 2020.05.03

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 시작점부터 시간 안에 갈 수 있는 곳을 탐색한다.

2. 갈 수 있는 곳의 개수를 세어 출력한다.

​

<해법>

1. 7가지 지하터널 표기 방법

=> 맵 입력을 받을 때, 있는 그대로의 숫자를 받는 대신 그 숫자가 가진 의미를 맵에 저장합니다.

 

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
105
106
107
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct tunnel {
    //좌표
    int x, y;
};
 
const int MAX = 50;
 
//북,동,남,서
//연결가능 = 1, 연결불가능 = 0
int shape[8][4] ={ 
    {0,0,0,0},
    {1,1,1,1},    //1번 모양 => 북,동,남,서 방향 연결가능
    {1,0,1,0},    //2번 모양 => 북,남 방향 연결가능
    {0,1,0,1},    //3번 모양 => 동,서 방향 연결가능
    {1,1,0,0},
    {0,1,1,0},
    {0,0,1,1},
    {1,0,0,1} 
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, M, R, C, L;
int map[MAX][MAX][4];
bool visited[MAX][MAX];
int res;
 
void bfs(tunnel start) {
    //처음 흉악범 탈출 지점 -> 1시간 후
    queue<tunnel> q;
    q.push(start);
    visited[start.x][start.y] = true;
    L--;
    res++;
 
    //시간이 종료될 때 까지
    while (L--) {
        //그 시간대에 갈 수 있는 모든 곳 탐색
        int qsize = q.size();
        for (int i = 0; i < qsize; i++) {
            tunnel cur = q.front();
            q.pop();
 
            for (int j = 0; j < 4; j++) {
                tunnel nxt = cur;
                nxt.x += di[j];
                nxt.y += dj[j];
 
                //범위를 벗어났을 경우 continue
                if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= M) {
                    continue;
                }
                
                //1. 현재 터널에서 가는 방향으로 뚫려있고,
                //2. 다음 터널에서 오는 방향으로 뚫려있고,
                //3. 이전에 방문했던 적이 없는 경우
                if (map[cur.x][cur.y][j] == 1 && map[nxt.x][nxt.y][(j + 2) % 4] && !visited[nxt.x][nxt.y]) {
                    visited[nxt.x][nxt.y] = true;
                    q.push(nxt);
                    res++;
                }            
            }
        }
    }
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
        
        //입력
        cin >> N >> M >> R >> C >> L;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //맵 입력을 받을 때, 그 곳에서 가능한 방향도 같이 저장
                int tmp;
                cin >> tmp;
                for (int k = 0; k < 4; k++) {
                    map[i][j][k] = shape[tmp][k];
                }
            }
        }
 
        //사용할 메모리 초기화
        memset(visited, false, sizeof(visited));
        res = 0;
        tunnel start = { R,C };
 
        //탐색 시작
        bfs(start);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
}

 

구현과 BFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글

[C++] SWEA 1238 - Contact  (0) 2020.05.03
[C++] SWEA 1219 - 길찾기  (0) 2020.05.03
[C++] SWEA 1209 - Sum  (0) 2020.05.03
[C++] SWEA 1954 - 달팽이 숫자  (0) 2020.05.03
[C++] SWEA 1974 - 스도쿠 검증  (0) 2020.05.03

+ Recent posts

티스토리툴바