순간을 성실히, 화려함보단 꾸준함을

[boj : 2615]오목 본문

알고리즘,SQL/백준,BOJ

[boj : 2615]오목

폭발토끼 2019. 6. 26. 17:22

[문제] : https://www.acmicpc.net/problem/2615

 

2615번: 오목

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림

www.acmicpc.net

[분류] : 구현

 

[조건] :

6개가 연속으로 존재하면 안된다.그 외에는 특별히 주의할게 없어 보입니다.

 

[구현과정]:

너무 화났던 문제입니다.(실력부족이죠,,,)

일일히 for문으로 구현해주었습니다.(가로,세로,대각선 X)

 

소스:(일단 제 소스는 그냥 참고만 하세요)

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
#include<iostream>
 
using namespace std;
 
int r, c;
int map[19][19];
 
int row(int x,int y, int b);
int col(int x,int y, int b);
int X(int x, int y, int b);
int X2(int x, int y, int b);
 
int main()
{
    int black=0,white=0;
    
    for (int i = 0; i < 19; i++)
        for (int j = 0; j < 19; j++)
            cin >> map[i][j];
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++)
            if (map[i][j] == 1)
            {
                black = row(i,j, map[i][j]);
                if (black == 1)break;
                black = col(i,j, map[i][j]);
                if (black == 1)break;
                black = X(i, j, map[i][j]);
                if (black == 1)break;
                black = X2(i, j, map[i][j]);
                if (black == 1)break;
            }
        if (black != 0)
            break;
    }
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19; j++)
            if (map[i][j] == 2)
            {
                white = row(i,j, map[i][j]);
                if (white == 1)break;
                white = col(i,j, map[i][j]);
                if (white == 1)break;
                white = X(i, j, map[i][j]);
                if (white == 1)break;
                white = X2(i, j, map[i][j]);
                if (white == 1)break;
            }
        if (white != 0)
            break;
    }
    //cout << black << " " << white<<"\n";
    if (black== white)
        cout << 0;
    else if (black == 1 && white == 0)
    {
        cout << 1 << "\n";
        cout << r + 1 << " " << c + 1;
    }
    else {
        cout << 2<<"\n";
        cout << r+1 << " " << c+1;
    }
}
int row(int x,int y, int b)
{
    int i;
    int cnt = 0;
    for (i = y; i < 19; i++)
    {
        if (map[x][i] != b)
            break;
        cnt++;
    }
    for (i = y; i >= 0; i--)
    {
        if (map[x][i] != b)
            break;
        cnt++;
    }
    if ((cnt - 1) == 5)
    {
        r = x;
        c = i + 1;
        return 1;
    }
    else
        return 0;
}
int col(int x,int y, int b)
{
    int cnt = 0;
    int i;
    for (i = x; i < 19; i++)
    {
        if (map[i][y] != b)break;
        cnt++;
    }
    for (i = x; i >= 0; i--)
    {
        if (map[i][y] != b)break;
        cnt++;
    }
    if ((cnt - 1) == 5)
    {
        r = i + 1;
        c = y;
        return 1;
    }
    else
        return 0;
}
int X(int x, int y, int b)
{
    int p = x, q = y;    
    int cnt = 0;
    while (p >= 0 && q >= 0 && p < 19 && q < 19)
    {
        if (map[p][q] != b)break;
        cnt++;
        p++;
        q++;
    }    
    p = x;
    q = y;    
    while (p >= 0 && q >= 0 && p < 19 && q < 19)
    {
        if (map[p][q] != b)break;
        cnt++;
        p--;
        q--;
    }
    if (cnt - 1 == 5)
    {
        r = p + 1;
        c = q + 1;
        return 1;
    }
    else
        return 0;
}
int X2(int x, int y, int b)
{
    int p = x, q = y;
    
    int cnt = 0;
    while (p >= 0 && q >= 0 && p < 19 && q < 19)
    {
        if (map[p][q] != b)break;
        cnt++;
        p--;
        q++;
    }
    p = x;
    q = y;
    while (p >= 0 && q >= 0 && p < 19 && q < 19)
    {
        if (map[p][q] != b)break;
        cnt++;
        p++;
        q--;
    }
    if (cnt-1 == 5)
    {
        r = p - 1;
        c = q + 1;
        return 1;
    }
    else
        return 0;
}
 

 

※gaelim님께 감사드립니다.

다른 분들의 소스를 보니 저와는 너무나도 다르게 소스들이 간결하더라구요.그래서 다른 분들 중 한명인 gaelim의 소스를 제시 하면서 설명하겠습니다.

 

[구현방법]:

오목판을 검색할때 결국은 왼쪽부터 검색하게 됩니다.이말은 즉슨 오목돌이 존재하는 좌표(x,y)보다 왼쪽이나 위로 확인했을때 오목돌이 존재한다면 해당 오목돌은 무시해도 됩니다.이미 전의 오목돌로 인해 검색이 된 오목돌이니까요.

이렇게 되면 오목돌 5개만 확인하면 됩니다.이 검색이 끝난 후 그 다음 칸에 오목돌이 존재하게 된다면 연속된 오목돌이 6개 이상이 된다는 뜻이므로 이 또한 정답이 될 수가 없어지죠.

이런방식으로 풀면 훨씬 코드짜는 시간도 짧아지고 수도 줄어들게 됩니다.

 

gaelim님의 소스 :

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
#include <cstdio>
 
int a[20][20];
int dx[4] ={-1, 1, 1, 0};
int dy[4] ={1, 0, 1, 1};
 
int chk(int x, int y, int d){
  int now=a[x][y];
  if ( a[x-dx[d]][y-dy[d]] == now) return 0;
  for (int i=1; i<=5; i++){
    if ( a[x][y] != now) return 0;
    x+=dx[d]; y+=dy[d];
  }
  return a[x][y]!=now;
}
 
int main(){
  for (int i=0; i<19; i++)
    for (int j=0; j<19; j++)
      scanf("%d", &a[i][j]);
 
  for (int i=0; i<19; i++){
    for (int j=0; j<19; j++){
      if (a[i][j]){
        for (int k=0; k<4; k++){
          if (chk(i, j, k)) return !printf("%d\n%d %d\n", a[i][j], i+1, j+1);
        }
      }
    }
  }
  printf("0\n");
}
 
 

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다

'알고리즘,SQL > 백준,BOJ' 카테고리의 다른 글

[boj : 16434] 드래곤 앤 던전  (0) 2019.07.02
[boj : 12865]평범한 배낭  (0) 2019.06.28
[boj : 16932]모양 만들기  (3) 2019.06.27
[boj : 14501]퇴사  (0) 2019.06.25
[boj : 9207] 페그 솔리테어  (4) 2019.06.25
'알고리즘,SQL/백준,BOJ' Related Articles more