https://www.acmicpc.net/problem/2615
2615번: 오목
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림
www.acmicpc.net
|
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
|
#include <iostream>
int arr[20][20];
int check[4][20][20];
int ans_x, ans_y;
int winner;
int dy[5] = { 9999, 1, -1, 0, 1 };
int dx[5] = { 9999, 0, 1, 1, 1 };
void input()
{
for (int i = 1; i < 20; ++i)
for (int j = 1; j < 20; ++j)
std::cin >> arr[i][j];
}
void print()
{
std::cout << '\n';
for (int y = 1; y < 20; ++y)
{
for (int x = 1; x < 20; ++x)
//std::cout << check[y][x] << ' ';
std::cout << '\n';
}
std::cout << '\n';
}
bool find_winner(int y, int x, int elem, int idx, int stk)
{
while (true)
{
if ((19 < y || 19 < x || x < 1 || y < 1) || arr[y][x] != elem)
{
break;
}
check[idx - 1][y][x] = idx;
y += dy[idx];
x += dx[idx];
++stk;
}
if (stk == 5)
{
return true;
}
return false;
}
void solve()
{
for (int x = 1; x < 20; ++x)
{
for (int y = 1; y < 20; ++y)
{
if (arr[y][x] == 1)
{
for (int i = 1; i <= 4; ++i)
{
if (check[i - 1][y][x] == i)
{
continue;
}
if (find_winner(y, x, arr[y][x], i, 0))
{
ans_y = y;
ans_x = x;
winner = arr[y][x];
return;
}
//print();
}
}
}
}
}
void output()
{
std::cout << winner << '\n';
if (winner != 0)
{
std::cout << ans_y << ' ' << ans_x;
}
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
틀린 방법. 6목을 판단하기 위해 굳이 배열을 네개나 더 넣어서 메모리를 뺄 필요가 없이
돌을 검사할 때 진행방향 바로 반대에 돌이 있는지만 검사한다면 훨씬 더 효율적인 코드를 짤 수 있다.
|
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
|
#include <iostream>
int arr[20][20];
int ans_x, ans_y;
int winner;
int dy[5] = { 9999, 1, -1, 0, 1 };
int dx[5] = { 9999, 0, 1, 1, 1 };
void input()
{
for (int i = 1; i < 20; ++i)
for (int j = 1; j < 20; ++j)
std::cin >> arr[i][j];
}
bool find_winner(int y, int x, int elem, int idx, int stk)
{
while (true)
{
if ((19 < y || 19 < x || x < 1 || y < 1) || arr[y][x] != elem)
{
break;
}
y += dy[idx];
x += dx[idx];
++stk;
}
if (stk == 5)
{
return true;
}
return false;
}
void solve()
{
for (int x = 1; x < 20; ++x)
{
for (int y = 1; y < 20; ++y)
{
if (arr[y][x] != 0)
{
for (int i = 1; i <= 4; ++i)
{
if (arr[y - dy[i]][x - dx[i]] == arr[y][x])
{
continue;
}
if (find_winner(y, x, arr[y][x], i, 0))
{
ans_y = y;
ans_x = x;
winner = arr[y][x];
return;
}
}
}
}
}
}
void output()
{
std::cout << winner << '\n';
if (winner != 0)
{
std::cout << ans_y << ' ' << ans_x;
}
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
미련한놈...
'알고리즘' 카테고리의 다른 글
| koi : 리모콘(dfs, bfs) (0) | 2020.04.24 |
|---|---|
| 백준 10971 : 외판원 순회 2 & koi : 연구활동 가는길 (0) | 2020.04.24 |
| 백준 7573 : 고기잡이 (0) | 2020.04.20 |
| 백준 2622 : 삼각형 만들기 (0) | 2020.03.28 |
| 완전탐색, 전체탐색법 (0) | 2020.03.26 |