[Java] 백준(실버-1) 2615번 - 오목
문제 풀이
이번 문제는 너비 우선 탐색인 BFS를 잘 응용하면 풀 수 있는 문제이다.
아이디어 도출
문제의 요구사항을 보면, 연속으로 5알이 놓인 오목은 정상이나, 6알인 육목이나 7알인 칠목의 경우는 조건 달성 실패라고 한다. 예륻 들어 흰돌이 6알, 검은돌이 5알이면 흰돌이 아닌 검은돌이 이기는 것이다.
먼저 오목판의 길이는 최대 19이기에 시간복잡도 측면에서 크게 걱정하지 않겠다고 느꼈고, 연속적으로 놓인 5알을 1칸씩 이동하며 찾을 방법을 BFS를 떠올리게 되었다.
1
2
static int[] dx = new int[]{0, 1, 0, -1, 1, -1, 1, -1};
static int[] dy = new int[]{1, 0, -1, 0, 1, 1, -1, -1};
먼저 오목의 경우 대각선 방향을 고려해야 하기에 상,하,좌,우 대각선까지 8방향으로 탐색을 해야한다고 생각했다. 그런데 8 방향으로 모두 탐색할 경우, 5알이 놓였는지, 5알 이상이 놓였는지를 구하기가 매우 까다로웠다.
1
2
3
// 가로, 세로, 오른쪽 위 대각선, 왼쪽 위 대각선 4 방향으로 탐색하기 위한 dx, dy 배열
static int[] dx = new int[]{1, 0, 1, -1};
static int[] dy = new int[]{1, 1, 0, 1};
그래서 8 방향으로 탐색하는 것이 아니라 가로, 세로, 오른쪽 대각선, 왼쪽 대각선만을 생각하여 탐색하는데, 연속으로 4알 이상이 놓인 돌일 경우, 진행방향의 반대방향에 같은 돌이 놓였는지 함께 체크하면서 탐색하도록 진행하였다.
이를 통해 아이디어를 정리해보자.
- 오목판 2차원 배열을 입력받고, 검은돌(1)과 흰돌(2)일 경우 가로(1,0), 세로(0,1), 오른쪽 위 대각선(1,1), 왼쪽 위 대각선(-1,1) 4 방향으로 BFS 탐색을 진행한다.
- 4 방향마다 이어진 같은 돌이 놓였는지 체크하면서, 오목이 놓였는지를 확인한다.
- 5알이 놓였을 경우 처음 돌이 놓인 시작위치의 반대 4 방향으로 탐색하며 6알 이상이 놓였는지 추가로 체크한다.
- 특정 알의 진행방향과 반대방향 모두 확인하여 5알인 오목이 놓였을 경우 해당 돌이 이긴 것으로 간주하여 해당 돌의 색상과 오목판의 위치를 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
import java.io.*;
import java.util.*;
class Main {
// 가로, 세로, 오른쪽 위 대각선, 왼쪽 위 대각선 4 방향으로 탐색하기 위한 dx, dy 배열
static int[] dx = new int[]{1, 0, 1, -1};
static int[] dy = new int[]{1, 1, 0, 1};
// 입력배열과 방문 배열 선언
static int[][] arr;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
arr = new int[19][19];
for(int i=0; i<19; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<19; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0; i<19; i++) {
for(int j=0; j<19; j++) {
// 오목판에 검은돌과 흰돌일 경우만 BFS를 수행한다.
if(arr[i][j] != 0) {
for(int k=0; k<4; k++) {
int cnt = bfs(i, j, k);
if(cnt == 5) {
bw.write(arr[i][j]+"\n");
bw.write((i+1) + " " + (j+1)+"\n");
return;
}
}
}
}
}
// 위 탐색과정에서 return 되지 않으면 승부가 결정나지 않았기에 0을 출력한다.
bw.write("0" + "\n");
}
}
// 오목판 배열을 탐색할 BFS 함수
public static int bfs(int x, int y, int dir) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(x, y, 1));
// 특정 돌의 연속으로 놓여진 갯수
int max = 0;
while(!q.isEmpty()) {
Node now = q.poll();
max = Math.max(max, now.cnt);
int i = now.x + dx[dir];
int j = now.y + dy[dir];
// 오목판 범위를 벗어나는지 체크한다.
if(!isRange(i, j)) {
continue;
}
// 흰돌은 흰돌끼리, 검은돌은 검은돌끼리 탐색할 돌이 같은 돌인지 체크한다.
if(arr[i][j] != arr[now.x][now.y]) {
continue;
}
q.offer(new Node(i, j, now.cnt+1));
}
/**
* 흰돌과 검은돌 중 오목을 달성했을 때,
* 해당 돌이 6개 이상인지를 확인하기 위해 시작돌의 반대방향을 체크한다.
*/
if(max == 5) {
int i = x - dx[dir];
int j = y - dy[dir];
// 오목판 범위는 벗어나지 않고 같은 돌이라면 육목 이상이다.
if(isRange(i, j) && arr[i][j] == arr[x][y]) {
max++;
}
}
return max;
}
// 오목판 배열 범위 체크 함수
public static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<19 && y<19) {
return true;
}
return false;
}
}
// 이동할 돌의 위치와 이어진 갯수를 담을 클래스
class Node {
int x;
int y;
int cnt;
Node(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.