[백준 P2615] 오목 자바 Java
P2615
문제
2615번: 오목
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호
www.acmicpc.net
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력값
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0출력값
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
1
3 20알고리즘
이 문제에서 탐색 방향은 중요하지 않다. 이 문제에서는 아래 그림의 검정색 화살표 방향과 파란색 화살표 방향이 같은 조합을 나타내기 때문이다. 따라서 몇 개의 돌이 연속적으로 있는지만 확인하면 되므로 델타를 활용하여 8방 탐색을 하지 않고 4방 탐색만 진행했다.
// 8방을 모두 탐색할 필요는 없음
public static final int[] dr = {-1, 0, 1, 1};
public static final int[] dc = {1, 1, 1, 0};
배열의 요소를 순회하면서 만약 돌이 있다면, 즉 0이 아니라면 위에서 설정한 4개의 방향을 검색한다. 각 방향으로 4번씩 가보면서 돌이 없거나 다른 색의 돌이 발견되면 더 이상 탐색하지 않고 넘어간다.
// 4방 탐색
for (int i = 0; i < 4; i++) {
int newR = r + dr[i];
int newC = c + dc[i];
isAble = true;
// 일단 4번 가본다. 가다가 다른 돌이 나오거나 빈 공간이 나오면 탐색을 종료한다.
for (int j = 0; j < 4; j++) {
if (0 < newR && newR <= MAP_SIZE && 0 <= newC && newC <= MAP_SIZE) {
if (map[newR][newC] == current) {
newR += dr[i];
newC += dc[i];
} else {
isAble = false;
break;
}
} else {
isAble = false;
break;
}
}
}만약 특정 방향에서 시작해서 4번 움직였을 때 모두 같은 종류의 돌이 발견되어 반복문이 끝났다면, 일단 5개의 연속적인 돌을 발견한 상태이다. 문제의 설명에 따르면 5목이 넘어가는 6목 또는 그 이상은 이긴 것으로 보지 않기 때문에 최종적으로 5개 초과의 돌이 연속되었는지 확인해야 한다.
이는 돌의 시작 위치에서 진행 방향 하나 전의 돌과, 돌의 끝 위치에서 진행 방향 하나 이후의 돌을 확인하면 된다. 만약 둘 중 하나의 돌이라도 연속된 돌과 색이 같다면 5목이 넘어가므로 다른 돌을 탐색한다. 이 때 돌의 시작 위치 하나 전이나 끝 위치 하나 이후가 오목판의 경계를 넘어가지 않도록 조건을 줘야 한다.
if (isAble) {
// 여기까지 왔다는 것은 일단 5개의 연속적인 돌을 탐색 완료 했다는 것이다. 따라서 그 돌의 양 옆이 다른 종류의 돌이거나 빈 공간이면 승리한다.
// 마지막 돌이 경계인 경우 예외처리를 위해 0과 MAP_SIZE + 1값도 포함
if (0 <= newR && newR <= MAP_SIZE + 1 && 0 <= newC && newC <= MAP_SIZE + 1) {
if (map[newR][newC] == current) {
isAble = false;
}
} else {
isAble = false;
}
}
if (isAble) {
newR = r - dr[i];
newC = c - dc[i];
if (0 <= newR && newR <= MAP_SIZE + 1 && 0 <= newC && newC <= MAP_SIZE + 1) {
if (map[newR][newC] == current) {
isAble = false;
} else {
winner = current;
winR = r;
winC = c;
break;
}
} else {
isAble = false;
}
}풀이 순서
- 게임판을 순회하면서 돌이 놓인 곳을 찾는다.
- 돌이 놓여 있다면 4개의 방향으로 각각 4칸을 이동해본다.
- 다른 색의 돌이 발견되면 1로 돌아간다.
- 4번 이동하는 동안 같은 색의 돌만 발견됐다.
- 연속하는 돌의 앞 부분과 뒷 부분이 경계를 넘어갔는지 확인한다.
- 연속하는 돌의 앞 부분과 뒷 부분이 같은 색인지 확인한다.
- 앞 부분과 뒷 부분이 다른 색이거나 경계를 넘어갔다면 5목을 발견한 것이므로 우승자와 돌의 좌료를 리턴한다.
- 그렇지 않다면 1으로 돌아간다.
코드
import java.util.*;
import java.io.*;
public class Main {
// 8방을 모두 탐색할 필요는 없음
public static final int[] dr = {-1, 0, 1, 1};
public static final int[] dc = {1, 1, 1, 0};
public static final int MAP_SIZE = 19;
public static int[][] map = new int[MAP_SIZE + 2][MAP_SIZE + 2];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int r = 1; r <= MAP_SIZE; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 1; c <= MAP_SIZE; c++) {
map[r][c] = Integer.parseInt(st.nextToken());
}
}
int winner = 0;
int winR = 0;
int winC = 0;
boolean isAble = true;
for (int r = 1; r <= MAP_SIZE; r++) {
for (int c = 1; c <= MAP_SIZE; c++) {
if (map[r][c] != 0) {
int current = map[r][c];
// 4방 탐색
for (int i = 0; i < 4; i++) {
int newR = r + dr[i];
int newC = c + dc[i];
isAble = true;
// 일단 4번 가본다. 가다가 다른 돌이 나오거나 빈 공간이 나오면 탐색을 종료한다.
for (int j = 0; j < 4; j++) {
if (0 < newR && newR <= MAP_SIZE && 0 <= newC && newC <= MAP_SIZE) {
if (map[newR][newC] == current) {
newR += dr[i];
newC += dc[i];
} else {
isAble = false;
break;
}
} else {
isAble = false;
break;
}
}
if (isAble) {
// 여기까지 왔다는 것은 일단 5개의 연속적인 돌을 탐색 완료 했다는 것이다. 따라서 그 돌의 양 옆이 다른 종류의 돌이거나 빈 공간이면 승리한다.
// 마지막 돌이 경계인 경우 예외처리를 위해 0과 MAP_SIZE + 1값도 포함
if (0 <= newR && newR <= MAP_SIZE + 1 && 0 <= newC && newC <= MAP_SIZE + 1) {
if (map[newR][newC] == current) {
isAble = false;
}
} else {
isAble = false;
}
}
if (isAble) {
newR = r - dr[i];
newC = c - dc[i];
if (0 <= newR && newR <= MAP_SIZE + 1 && 0 <= newC && newC <= MAP_SIZE + 1) {
if (map[newR][newC] == current) {
isAble = false;
} else {
winner = current;
winR = r;
winC = c;
break;
}
} else {
isAble = false;
}
}
}
}
if (winner != 0) {
break;
}
}
if (winner != 0) {
break;
}
}
if (winner == 0) {
System.out.println(0);
} else {
System.out.println(winner);
System.out.printf("%d %d\n", winR, winC);
}
}
}