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


1. 문제 이해

  

 삼성 기출 문제 입니다. 

 시뮬레이션 문제인데, 과정을 자세히 보면 dfs와는 다른것을 볼 수 있습니다.

처음에 이 문제를 dfs로 접근 하였다가 멘토님의 도움으로 while문으로 해결하는 문제라는것을 깨닳았습니다.


(그러니... 꼭 다시 풀어보자!!)



2. 접근 방법


 문제의 루틴대로 따라가면서 while문을 작성해 봅시다.

여기서 핵심은 flag!!


1) 4방향을 모두 탐색하였는데, 청소할곳(0)을 못찾은 경우에 루틴으로 가기 위한 flag!


2) 뒤로 가봤는데 뒤에가 벽인 경우는 탈출할수 있도록!!


3) 뒤로 가봤는데 뒤에가 벽이 아닌 경우는 방향을 그대로 가져 가도록 합시다!!


위에 3가지를 생각하면서 코딩에 들어가면 문제 끄~~~읏!!!



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>
#define MAX_SIZE 50
using namespace std;
 
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
int n, m;
int map[MAX_SIZE][MAX_SIZE];    // 1:벽, 2:청소
 
int next_dir(int d) {
    return (d + 1) % 4;
}
 
bool map_impossible(int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= n) return 1;
    return 0;
}
 
int main() {
 
    int r, c, d;
 
    cin >> n >> m;
    cin >> r >> c >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int x = c, y = r;
 
    if (d == 1) d = 3;
    else if (d == 3) d = 1;
 
    int res = 0;
    while (true) {
 
        if (map[y][x] == 0) {
            map[y][x] = 2;
            res++;
        }
 
        bool search_flag = false;
 
        for (int i = 0; i < 4; i++) {
            d = next_dir(d);
 
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (map_impossible(nx, ny) || map[ny][nx] != 0) continue;
 
            x = nx;
            y = ny;
            search_flag = true;
            break;
        }
 
        if (search_flag) continue;
 
        // 4방향 모두 못찾았을 때
 
        d = next_dir(d + 1);    // 뒷 방향
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if (map_impossible(nx, ny) || map[ny][nx] == 1) break;
 
        // 뒤가 벽이 아니면 
        d = next_dir(d + 1);    // 방향 유지한 채
        x = nx;                    // 뒤로 가기
        y = ny;
    }
 
    cout << res << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

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

[HASH] 완주하지 못한 선수  (0) 2019.11.02
#2178. 미로탐색  (0) 2018.12.24
#14891. 톱니바퀴  (0) 2018.01.17
#14502. 연구소  (4) 2018.01.16
#1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2018.01.07

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


1. 문제 이해


 이 문제를 풀면서 하나 깨닳은 것은 문제 이해가 개인적으로 정말 중요하다는것을 느꼈습니다....

 뱀문제와 마찬가지로 시뮬레이션 문제 입니다.


2. 접근 방법


[1 단계] 입력되는 dir변수에 따라서 시계방향으로 돌지, 반 시계방향으로 돌지 정하게 됩니다.


[2 단계] 왼쪽, 오른쪽을 검사하여 서로 다른 값이 있다면 반대방향으로 돌려주고, 

                                   서로 같은 값이 있다면 돌려 움직이지 않습니다.


=> 저같은 경우는 이 부분을 왼쪽 오른쪽 으로 나눠서 재귀로 작성하였습니다.


cf> 이 부분에서 논리적으로 잘못생각하여 시간이 꽤 걸렸습니다.

 돌리기전에 양옆을 먼저 확인하여 옆 톱니가 움직이는지 여부를 먼저 결정해줘야 합니다!!!


[3 단계] 12시 방향에 있는것들의 가중치를 곱해 답을 출력합니다.


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
#include <cstdio>
 
using namespace std;
 
int res;
int gear[5][8];
 
void rotate_gear(int n, int d) {
    if (d == 1) {            // 시계방향
        int tmp = gear[n][7];
        for (int i = 6; i >= 0; i--) {
            gear[n][i + 1] = gear[n][i];
        }
        gear[n][0] = tmp;
    }
    else if (d == -1) {        // 반 시계 방향
        int tmp = gear[n][0];
        for (int i = 1; i < 8; i++) {
            gear[n][i - 1] = gear[n][i];
        }
        gear[n][7] = tmp;
    }
}
 
void move_right(int n, int d) {
    if (!(1 <= n && n <= 4)) return;
 
    if (gear[n - 1][2] != gear[n][6]) {
        d = (d == 1) ? -1 : 1;
        move_right(n + 1, d);
        rotate_gear(n, d);
    }
}
 
void move_left(int n, int d) {
    if (!(1 <= n && n <= 4)) return;
 
    if (gear[n][2] != gear[n + 1][6]) {
        d = (d == 1) ? -1 : 1;
        move_left(n - 1, d);
        rotate_gear(n, d);
    }
}
 
int main() {
    for (int i = 1; i < 5; i++) {
        for (int j = 0; j < 8; j++) {
            scanf("%1d", &gear[i][j]);
        }
    }
 
    int k;
    scanf("%d", &k);
 
    for (int i = 0; i < k; i++) {
        int bun, dir;
        scanf("%d %d", &bun, &dir);
 
        move_left(bun - 1, dir);
        move_right(bun + 1, dir);
 
        rotate_gear(bun, dir);
    }
 
    res = gear[1][0] + (2 * gear[2][0]) + (4 * gear[3][0]) + (8 * gear[4][0]);
 
    printf("%d\n", res);
    return 0;
}
cs


저작자표시 비영리 변경금지

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

#2178. 미로탐색  (0) 2018.12.24
#14503. 로봇 청소기  (1) 2018.01.22
#14502. 연구소  (4) 2018.01.16
#1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2018.01.07
#1759. 암호 만들기  (0) 2017.12.29

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


1. 문제 이해


 벽을 3개 세웠을때, 바이러스가 퍼지고, 그후 바이러스에 전염되지 않은지역을 세는 문제입니다. 이때, 전염되지 않은 지역이 최대가 되는 경우를 알아내는 문제입니다. 


2. 접근 방법


 n이 8보다 작은수 이므로 완전 탐색으로 해결했습니다.


[1단계] dfs로 벽 세우기 (for문을 사용한 완전 탐색)


[2단계] 벽이 3개가 됐을때, bfs로 바이러스 확장시키기


[3단계] 바이러스를 퍼지기 전으로 회복시키면서 전염이 안된 지역 세어주기


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
#include <cstdio>
#include <vector>
#include <queue>
#define MAX_SIZE 8
 
using namespace std;
 
int n, m;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int map[MAX_SIZE][MAX_SIZE];    // 1:벽, 2:바이러스
int visit[MAX_SIZE][MAX_SIZE];
vector <pair <int, int> > virus;
int _max = 0;
 
int recovery_map(int(* a)[MAX_SIZE], int(* b)[MAX_SIZE]) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0) ret++;
            b[i][j] = a[i][j];
        }
    }
    return ret;
}
 
void copy_map(int(* a)[MAX_SIZE], int (* b)[MAX_SIZE]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = b[i][j];
        }
    }
}
 
void bfs() {
    queue <pair<int, int> >q;
    for (int i = 0; i < virus.size(); i++) {
        q.push(virus[i]);
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if (map[ny][nx] != 0) continue;
 
            map[ny][nx] = 2;
            q.push(make_pair(nx, ny));
        }
 
    }
}
 
void make_wall(int x, int y, int d) {
    map[y][x] = 1;
    visit[y][x] = 1;
 
    if (d == 3) {
 
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
        bfs();
        int buf = recovery_map(tmp, map);
        _max = _max < buf ? buf : _max;
 
        map[y][x] = 0;
        visit[y][x] = 0;
        return;
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != 0 || visit[i][j]) continue;
            make_wall(j, i, d + 1);
        }
    }
    map[y][x] = 0;
    visit[y][x] = 0;
 
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) virus.push_back(make_pair(j, i));
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != 0) continue;
            make_wall(j, i, 1);
        }
    }
 
    printf("%d\n", _max);
    return 0;
}

cs


저작자표시 비영리 변경금지

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

#14503. 로봇 청소기  (1) 2018.01.22
#14891. 톱니바퀴  (0) 2018.01.17
#1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2018.01.07
#1759. 암호 만들기  (0) 2017.12.29
#2140. 지뢰찾기  (0) 2017.12.29

+ Recent posts

티스토리툴바