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/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

티스토리툴바