문제
https://www.acmicpc.net/problem/2615
풀이
문제
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램
- 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이김
- 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻함
- 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
int[19][19]
각 좌표는 0, 1, 2로 표현됨
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력
검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력
int 1 or 2 or 0
int 좌표
풀이
범위 등에 관한 조건을 만났을 때 break하는지 continue하는지 확실하게 판단해서 코드를 구현하자!!! 여기서 시간 많이 뺏김
- 처음부터 돌면서 1 또는 2가 나오면 탐색 시작
- 오른쪽, 아래쪽, 왼쪽 아래, 오른쪽 아래에 같은 값이 존재하는지 탐색
- 탐색하면서 같은 숫자가 5개가 되고 그 다음에는 다른 숫자가 나왔을 때 해당 바둑알이 승리 -> 좌표 저장
- 탐색하면서 같은 숫자가 5개가 되고 그 다음에도 해당 숫자가 나오면 다른 시작점 탐색
- 탐색하면서 같은 숫자가 5개가 된 경우에 시작점 이전 방향도 같은 숫자라면 다음 방향 탐색
- 전부 탐색했는데도 승부가 안 되면 승부가 안 됨
- 모든 경우를 거치고 같은 숫자가 5개가 된 경우라면 chk = true로 변경 후 시작점 좌표 저장하여 출력!
코드
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj2615 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 오목 탐색 : 왼쪽아래, 아래, 오른쪽아래, 오른쪽
int[] dx = {-1, 0, 1, 1};
int[] dy = {1, 1, 1, 0};
int[][] board = new int[19][19]; // 바둑판
boolean chk = false;
int cnt = 0;
StringTokenizer st;
// 바둑판 설정
for(int i=0; i<19; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<19; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
StringBuilder sb = new StringBuilder();
int start = 0; // 바둑알
loop:for(int i=0; i<19; i++) {
for(int j=0; j<19; j++) {
if(board[i][j] == 1 || board[i][j] == 2) {
start = board[i][j];
for(int k=0; k<4; k++) {
cnt = 1; // cnt 초기화 조심
int goX = i+dx[k];
int goY = j+dy[k];
if(goX < 0 || goX >= 19 || goY < 0 || goY >= 19) continue;
// 범위 안 맞으면 다음 방향 탐색
// 범위가 맞다면 현재 방향으로 탐색 시작
else if( goX >= 0 && goX < 19 && goY >= 0 && goY < 19 ) {
while(board[goX][goY] == start) {
cnt++;
if(cnt > 5) {
// 같은 돌이 6개가 됐다면
chk = false; // 체크
break; // 그 다음 위치 탐색
}
// 조건에 만족하는 방향이라면 그 방향으로 쭉 진행하면서 탐색
goX += dx[k];
goY += dy[k];
if( goX < 0 || goX >= 19 || goY < 0 || goY >= 19 ) break;
//그 다음 위치 탐색하기 전에 배열 범위 조건이 맞지 않다면 반복문 빠져나옴
}
if(cnt == 5 && i-dx[k]>=0 && i-dx[k]<19 && j-dy[k]>=0 && j-dy[k]<19) {
if(board[i-dx[k]][j-dy[k]] == start) continue;
// 5번을 다하고 돌아왔을때 반대로 돌이 있는경우 6이된다.
// 거짓으로 판단. 다음 방향 탐색
}
// 모든 조건을 통과하고 같은 돌이 5개가 완성된 경우 출력
if(cnt == 5) {
chk = true;
sb.append(start+"\n");
sb.append((i+1)+" "+(j+1));
break loop;
}
}
}
}
}
}
if(chk) System.out.println(sb);
else System.out.println(0);
}
}
