그냥 문제에 주어진 조건대로 움직이기만 하면 끝나는 문제입니다.

말이 좀 난해하긴한데... 디버깅하면서 따라가니 이해가 가더라구요!

그림 그려보시면 편하실 것 같습니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
int sx, sy, sd;
 
//process
int max_value;
int dx[4] = { -1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
 
 
void input()
{
    scanf("%d %d", &m, &n);
    scanf("%d %d %d", &sx, &sy, &sd);
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
}
 
int turn(int now, int next)
{
    if(next == 0)//next == 0은 왼쪾으로 턴
    {
        if(now == 0) return 3;
        else if(now == 1) return 0;
        else if(now == 2) return 1;
        else return 2;
    }
    else return (now + 2) % 4;//0->2,2->0,1->3,3->1
}
 
 
void print()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            printf("%d ", map[i][j]);
        }
        puts("");
    }
    puts("");
}
 
void process()
{
    int x = sx;
    int y = sy;
    int d = sd;
    int cnt = 0;
 
    int ret = 1;
    map[x][y] = 2;
 
    int nx;
    int ny;
 
    while(1)
    {
        if(cnt == 4)
        {
            d = turn(d, 1);
            nx = x + dx[d];
            ny = y + dy[d];
 
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] == 1) break;
 
            x = nx;
            y = ny;
            d = turn(d, 1);
            cnt = 0;
            continue;
        }
 
        d = turn(d, 0);
        nx = x + dx[d];
        ny = y + dy[d];
 
        cnt++;
 
 
        if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
        x = nx;
        y = ny;
 
        map[x][y] = 2; // 청소함!
 
        ret++;
        cnt = 0;
    }
 
    printf("%d\n", ret);
}
 
int main()
{
    input();
    process();
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17

이 문제도 N이 작기 때문에 3개의 기둥을 한번씩 다 세워보고 최대값을 찾는 완전탐색 문제입니다.

dfs는 기둥을 세우는 함수이며, 깊이가 3이 되었을 때(기둥을 세개 세웠을 때) bfs함수를 호출합니다.

bfs는 바이러스가 퍼지는 함수 입니다. bfs가 끝나면 recovery함수를 호출해서 바이러스가 퍼지기 전의 맵 상태로 돌리며,

돌릴 때 0의 개수도 같이 세서 리턴하는 함수입니다.


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
132
133
134
135
136
137
138
139
140
141
142
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 8
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
 
vector<pair<int, int> > virus;
 
void input()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
 
            if(map[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
}
 
void copy_map(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
 
int recovery(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    int ret = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(a[i][j] == 0) ret++;
            a[i][j] = b[i][j];
        }
    }
    return ret;
}
 
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 || map[nx][ny] != 0) continue;
 
            map[nx][ny] = 2;
            q.push(make_pair(nx, ny));
        }
    }
}
 
void dfs(int x, int y, int d)
{
    map[x][y] = 1;
    visit[x][y] = 1;
 
    if(d == 3)
    {
        //bfs
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
 
        bfs();
        max_value = max(max_value, recovery(map, tmp));
 
        visit[x][y] = 0;
        map[x][y] = 0;
        return;
    }
 
    for(int i = x; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(visit[i][j] || map[i][j] != 0) continue;
            dfs(i, j, d + 1);
        }
    }
 
    map[x][y] = 0;
    visit[x][y] = 0;
}
 
void process()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] != 0) continue;
            dfs(i, j, 1);
        }
    }
 
    printf("%d\n", max_value);
}
 
int main()
{
    input();
    process();
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16

이 문제는.. N이 작아서 그냥 완전 탐색으로 해결했습니다.

결국 그 날에 그 고객을 상담하냐 안하냐 이 두가지 경우 뿐입니다.

굉장히 난이도가 낮은 문제입니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 16
#define INF 0x7fffffff
 
using namespace std;
//input
int cost[MAX_SIZE];
int day[MAX_SIZE];
int n;
 
//process
int max_value;
 
void input(){
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) scanf("%d %d", &day[i], &cost[i]);
}
 
void dfs(int d, int sum){
    if (d == n + 1){
        max_value = max(max_value, sum);
        return;
    }
 
    if(d + day[d] <= n + 1) dfs(d + day[d], sum + cost[d]);
    if(d + 1 <= n + 1) dfs(d + 1, sum);
}
 
void process(){
    dfs(1, 0);
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}
cs



디피로도 한번 풀어봤는데..

더 효율적인 점화식이 있다면 댓글 부탁드립니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
 
int day[MAX_SIZE];
int cost[MAX_SIZE];
int dp[MAX_SIZE];
 
int main(){
 
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", &day[i], &cost[i]);
 
    int ret = 0;
    for(int i = 1; i <= n; i++){
        int next1 = i + day[i];
        int next2 = i + 1;
 
        if(next1 <= n + 1) dp[next1] = max(dp[next1], dp[i] + cost[i]);
        if(next2 <= n + 1) dp[next2] = max(dp[next2], dp[i]);
 
        ret = max(max(ret, dp[next1]), dp[next2]);
    }
 
    printf("%d\n", ret);
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18
[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16

음... 테트리스의 모양 중에서 다른건 간단하게 생각하셨을 것 같은데...

凸이 모양이 좀 고민스러웠죠...

저는

위, 아래, 왼, 오른쪽으로 각각 가중치를 주었습니다. dfs 매개변수에서 weight라는 변수입니다.

위 = 1

아래 = 10

왼 = 100

오 = 1000

이렇게 각각 주어서

만약 세로로 세칸 짜리는 20이 될 것입니다.(0부터 시작하므로 2칸이동하면 20)

만약 가로로 세칸 짜리는 2000이 될 것입니다. 오른쪽으로 두 칸 갔기 때문입니다.

이 두가지 경우에는 추가로 2방향씩 더 검사해줍니다.

세로 방향일 경우에는 1시와 11시 대각선을 검사하고, (코드에서 (ddx[0], ddy[0]), (ddx[1], ddy[1]))

가로 방향일 경우에는 11시와 7시 방향의 대각선을 검사하면 됩니다. (코드에서 (ddx[2], ddy[2]), (ddx[3], ddy[3]))

모든 맵을 dfs하고 가장 큰 수를 출력하면 끝입니다.!


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 500
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ddx[4] = { -1, -1, -1, 1 };
int ddy[4] = { -1, 1, -1, -1 };
 
void input(){
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
}
 
int pow(int n, int r){
    if (r == 0) return 1;
    else if (r % 2 == 0){
        int tmp = pow(n, r / 2);
        return tmp *tmp;
    }
    else return pow(n, r - 1) * n;
}
 
void dfs(int x, int y, int d, int sum, int weight){
    if (d == 3){
        max_value = max(max_value, sum);
        return;
    }
 
    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 || visit[nx][ny]) continue;
 
        visit[x][y] = 1;
 
        dfs(nx, ny, d + 1, sum + map[nx][ny], weight + pow(10, i));
 
        visit[x][y] = 0;
    }
 
    if (weight == 20){
        for (int i = 0; i < 2; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
    else if (weight == 2000){
        for (int i = 2; i < 4; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
 
}
 
void process(){
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            dfs(i, j, 0, map[i][j], 0);
        }
    }
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16

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


이전의 글 중에서.. 불이라는 문제가 있는데요!!
그 문제랑 완전히 똑같다고 보시면됩니다!!!!!

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
106
107
108
109
110
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
 
#define MAX_SIZE 51
 
using namespace std;
 
typedef struct _data
{
    int x;
    int y;
    int sec;
    bool water;
} data;
 
int r, c;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int startx, starty;
int endx, endy;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<pair<int, int> > w;
 
//고슴도치 S
//동굴 D
//X는 벽
//*는 물
void input()
{
    scanf("%d %d", &r, &c);
    getchar();
 
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            scanf("%c", &map[i][j]);
 
            if(map[i][j] == 'S')
            {
                startx = i;
                starty = j;
            }
            else if(map[i][j] == 'D')
            {
                endx = i;
                endy = j;
            }
            else if(map[i][j] == '*')
            {
                w.push_back(make_pair(i, j));
            }
        }
        getchar();
    }
}
 
int bfs()
{
    queue<data> q;
    for(int i = 0; i < w.size(); i++) q.push(data{w[i].first, w[i].second, 0, 1});
    q.push(data{startx, starty, 0, 0});
 
    while(!q.empty())
    {
        data pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int t = pop_data.sec;
        bool water = pop_data.water;
 
        if(water == 0 && endx == x && endy == y) return t;
 
        if(!water && visit[x][y] == 1) continue;
        else if(!water && visit[x][y] == 0) visit[x][y] = 1;
 
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if(map[nx][ny] == 'X' || map[nx][ny] == '*') continue;
            if(water && map[nx][ny] == 'D') continue;
            if(water) map[nx][ny] = '*';
            q.push(data{nx, ny, t + 1, water});
        }
    }
 
    return -1;
}
 
int main()
{
    input();
    int ret = bfs();
    if(ret == -1) puts("KAKTUS");
    else printf("%d\n", ret);
 
 
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17
[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16

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


이 문제는 ..전형적인 BFS문제라고 할 수 있습니다..


제 주변에 큐를 두개를 써서 푸시는 분들이 꽤 계신데..


저는 큐를 하나를 썼습니다.

하나를 쓸 때 핵심은 불을 먼저 넣고 사람을 넣어야한다는 점입니다.

이유는 사람을 먼저 넣을 경우 불이 퍼지는 위치임을 알지 못하고 불에 휩싸여 죽을 수가 있기 때문입니다!

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
106
107
108
109
110
111
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX_SIZE 1000
 
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int sec;
    bool type;
} pos;
 
vector<pair<int, int> > v;//fire_pos
 
bool visit[MAX_SIZE][MAX_SIZE];
char map[MAX_SIZE][MAX_SIZE];
int n, m;
int sx, sy;
 
void input()
{
    scanf("%d %d", &n, &m);
    getchar();
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            char c = getchar();
            map[i][j] = c;
            if(c == '*') v.push_back(make_pair(i, j));
            else if(c == '@') sx = i, sy = j;
        }
        getchar();
    }
}
 
int bfs()
{
    queue<pos> q;
 
    for(int i = 0; i < v.size(); i++) q.push(pos{v[i].first, v[i].second, 0, 0});
    q.push(pos{sx, sy, 0, 1});
 
    visit[sx][sy] = 1;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
    while(!q.empty())
    {
        pos pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int sec = pop_data.sec;
        int type = pop_data.type;
 
        if(type && (x == 0 || x == m - 1|| y == 0 || y == n - 1)) return sec + 1;
 
        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[nx][ny] == '#' || map[nx][ny] == '*') continue;
            if(visit[nx][ny]) continue;
 
            if(type) visit[nx][ny] = 1;
            else map[nx][ny] = '*';
 
            q.push(pos{nx, ny, sec + 1, type});
        }
    }
 
    return 0;
}
 
void print()
{
    for(int i = 0; i < m; i++) printf("%s\n", map[i]);
}
 
int main()
{
    int t;
    scanf("%d", &t);
 
    for(int test_case = 0; test_case < t; test_case++)
    {
        v.clear();
        memset(visit, 0, sizeof(visit));
 
        input();
 
        int ret = bfs();
        if(ret) printf("%d\n", ret);
        else printf("IMPOSSIBLE\n");
    }
 
    return 0;
}
 
 
 
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[5214] 환승  (0) 2017.04.04

째로탈출 1과 2는 사실 같은 문제이지만.. 뭐..

그 중에서.. 어렵다면 2번이 더 어렵겠죠????

최적화해서 풀기도 했지만.. 이번에 올릴 코드는

최적화된 코드는아닙니다!

동서남북으로 각각 이동했다면 각각으로는 다시 이동하지 않게 만들면 최적화가 되겠지요???


문제 푸는 요령은... 공이 파랑, 빨강이 있습니다.. 이 문제는 우선순위만 판단할 수 있다면 그리 어려운 문제는 아니라고 생각합니다.

파랑과 빨강이 같은 행이나 열에 있는데.. 행이면 왼쪽, 오른쪽 열이면 위 아래로 움직일 때 우선순위를 판별해서 공의 위치만 정할 수 있으면

간단하게 해결할 수 있습니다. 공이 움직이는 함수는 move()입니다. 우선순위를 판별하는 함수는 priority_inspect입니다.

그냥 공이 한개라고생각하고 밀고나서 두 공의 위치가 같을 경우!!!! 우선순위를 판별하여 적절한 위치에 공을 놓으면 끝입니다!!!!!



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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define MAX_SIZE 11
#define INF 0x7fffffff
using namespace std;
 
char map[MAX_SIZE][MAX_SIZE];
int m, n;
int bx, by;
int rx, ry;
 
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
 
void input(){
    scanf("%d %d", &m, &n);
    getchar();
 
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            map[i][j] = getchar();
            if (map[i][j] == 'B'){
                bx = i;
                by = j;
            }
            else if (map[i][j] == 'R'){
                rx = i;
                ry = j;
            }
        }
        getchar();
    }
}
 
void print(){
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            printf("%c", map[i][j]);
        }
        puts("");
    }
    puts("");
}
 
bool priority_inspect(int d){//레드가 높으면 1 아니면 0
    switch (d){
    case 0:
        if (rx < bx) return 1;
        else return 0;
        break;
    case 1:
        if (rx > bx) return 1;
        else return 0;
        break;
    case 2:
        if (ry < by) return 1;
        else return 0;
        break;
    case 3:
        if (ry > by) return 1;
        else return 0;
        break;
    }
}
 
int move(int d){//위 아래 왼 오
 
    bool red_zero = 0, blue_zero = 0;
    bool red_stop = 0, blue_stop = 0;
    bool red_prio = priority_inspect(d);
    int nrx;
    int nry;
    int nbx;
    int nby;
 
    //둘다 못움직일 때 까지 와일
    while (!blue_stop || !red_stop){
 
        if (!red_stop){
            nrx = rx + dx[d];
            nry = ry + dy[d];
 
            if (nrx < 0 || nry < 0 || nrx >= m || nry >= n || map[nrx][nry] == '#') red_stop = 1;
            else if (map[nrx][nry] == 'O'){
                red_stop = 1;
                red_zero = 1;
            }
            else{
                rx = nrx;
                ry = nry;
            }
        }
 
        if (!blue_stop){
            nbx = bx + dx[d];
            nby = by + dy[d];
 
            if (nbx < 0 || nby < 0 || nbx >= m || nby >= n || map[nbx][nby] == '#') blue_stop = 1;
            else if (map[nbx][nby] == 'O'){
                blue_stop = 1;
                blue_zero = 1;
            }
            else{
                bx = nbx;
                by = nby;
            }
        }
    }
 
    //공의 위치가 같을 때
    if (rx == bx && ry == by){
        if (d == 0){
            if (red_prio) bx++;
            else rx++;
        }
        else if (d == 1) {
            if (red_prio) bx--;
            else rx--;
        }
        else if (d == 2) {
            if (red_prio) by++;
            else ry++;
        }
        else {
            if (red_prio) by--;
            else ry--;
        }
    }
 
    if (blue_zero) return 0; // 블루 제로 들어감
    else if (red_zero) return 1; // 레드 제로 들어감
    else return 2; // 제로 발견 못함
}
 
int dfs(int d){//깊이
    if (d == 10) return INF;
 
    int brx = rx;
    int bry = ry;
    int bbx = bx;
    int bby = by;
    int ret = INF;
 
    for (int i = 0; i < 4; i++){
        int tmp = move(i);
 
        if (tmp == 1) return d + 1;
        else if (tmp == 2){
            int tmp2 = dfs(d + 1);
            if (ret > tmp2) ret = tmp2;
        }
 
        rx = brx;
        ry = bry;
        bx = bbx;
        by = bby;
    }
 
    return ret;
}
 
 
int main(){
    //freopen("input.txt", "r", stdin);
    //setbuf(stdout, NULL);
 
    //int t;
    //scanf("%d", &t);
 
    //while (t--){
 
    input();
    int ret = dfs(0);
    printf("%d\n", ret == INF ? -1 : ret);
 
    //}
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[5214] 환승  (0) 2017.04.04
[9009] 피보나치  (0) 2017.04.04

처음에 풀었을 때는 0이 아닌부분을 다 밀어서 합쳤었는데..

스터디 중에 친구가 0이 아닌 부분은 다 큐에넣어서 처리하면 편하다고 해서 그렇게 해보았는데 

굉장히쉽더라구요???

0이아니면 방향대로 큐에 넣어서 큐에서 순서대로 꺼내며 같으면 합치는 방법으로 구현했습니다.

어려운 문제는 아닌 것 같습니다!!(처음에 풀 땐 굉장히 어려웠지만요..ㅠㅠ)

void merge()가 핵심 함수 인듯 싶습니다.



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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <iostream>
#include <queue>
 
#define MAX_SIZE 25
 
using namespace std;
 
int n;
int map[MAX_SIZE][MAX_SIZE];
int ret;
void merge(int d)
{
    queue<int> q;
    int cnt = 0;
 
 
    switch (d){
 
    case 0://위
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (map[j][i] != 0) q.push(map[j][i]);
                map[j][i] = 0;
            }
 
            int idx = 0;
            int pop_data;
 
            while (!q.empty()){
                pop_data = q.front();
                q.pop();
 
                if (map[idx][i] == 0) map[idx][i] = pop_data;
                else if (map[idx][i] == pop_data){
                    map[idx][i] *= 2;
                    idx++;
                }
                else map[++idx][i] = pop_data;
            }
 
        }
        break;
    case 1://아래
        for (int i = 0; i < n; i++){
            for (int j = n - 1; j >= 0; j--){
                if (map[j][i] != 0) q.push(map[j][i]);
                map[j][i] = 0;
            }
 
            int idx = n - 1;
            int pop_data;
 
            while (!q.empty()){
                pop_data = q.front();
                q.pop();
 
                if (map[idx][i] == 0) map[idx][i] = pop_data;
                else if (map[idx][i] == pop_data){
                    map[idx][i] *= 2;
                    idx--;
                }
                else map[--idx][i] = pop_data;
            }
        }
        break;
    case 2://왼
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (map[i][j] != 0) q.push(map[i][j]);
                map[i][j] = 0;
            }
 
            int idx = 0;
            int pop_data;
 
            while (!q.empty()){
                pop_data = q.front();
                q.pop();
 
                if (map[i][idx] == 0) map[i][idx] = pop_data;
                else if (map[i][idx] == pop_data){
                    map[i][idx] *= 2;
                    idx++;
                }
                else map[i][++idx] = pop_data;
            }
 
        }
        break;
 
    case 3://오
        for (int i = 0; i < n; i++){
            for (int j = n - 1; j >= 0; j--){
                if (map[i][j] != 0) q.push(map[i][j]);
                map[i][j] = 0;
            }
 
            int idx = n - 1;
            int pop_data;
 
            while (!q.empty()){
                pop_data = q.front();
                q.pop();
 
                if (map[i][idx] == 0) map[i][idx] = pop_data;
                else if (map[i][idx] == pop_data){
                    map[i][idx] *= 2;
                    idx--;
                }
                else map[i][--idx] = pop_data;
            }
        }
        break;
 
 
    }
}
 
void copy(int(*arr)[MAX_SIZE], int(*arr2)[MAX_SIZE]){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            arr[i][j] = arr2[i][j];
        }
    }
}
 
void dfs(int d)
{
    if (d == 5){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (map[i][j] > ret) ret = map[i][j];
            }
 
        }
        return;
    }
 
    int copymap[MAX_SIZE][MAX_SIZE];
    copy(copymap, map);
 
    for (int i = 0; i < 4; i++){
        merge(i);
        dfs(d + 1);
        copy(map, copymap);
    }
}
 
 
void input(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
}
 
void print(){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            printf("%d ", map[i][j]);
 
        puts("");
    }
}
 
int main(){
    input();
    dfs(0);
    printf("%d\n", ret);
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[5214] 환승  (0) 2017.04.04
[9009] 피보나치  (0) 2017.04.04
[9328] 열쇠  (0) 2017.04.02

+ Recent posts

티스토리툴바