1. 문제 분석
문제
1. 바둑판은 19 X 19
: 2차원의 배열을 생각할 수 있다. 또한 배열에 들어갈 요소가 0, 1, 2뿐이므로 정수형 또는 String형, Char형등 편한 것으로 배열 선언을 하면 된다.
추가적으로 탐색을 해야할 경우 padding이라는 잡기술(필요한 배열의 인덱스 길이보다 더 길게 생성하여 경계값을 표기하는 방법)을 통해 경계값 초과 여부를 처리할 수 있으므로 때에 잘 활용하면 좋다.-(해당 풀이의 경우 padding을 활용하지 않았다.)2. 흑과 백 두 플레이어 존재
: 문제 그대로 흑 1, 백 2로 숙지 해 두고 PASS3. 연속적으로 다섯 알일 경우 승리
: 같은 로직의 탐색이 필요한 경우 재귀를 사용하자. 또한 한 방향으로 연속 5번으로 같은 돌이 놓여있는 지 확인하기 위해 재귀 메서드 외의 count변수로 Static 접근자 활용도 떠올린다.
"재귀 내의 조건"
1. 다른 색의 돌(1이라면 2, 2라면 1)을 만났을 경우 재귀 끝 count값 return,
2. 바둑판 경계를 만나면 재귀 끝 count값 return,
3. 특정 방향의 값을 알고 있어야 한쪽 방향으로 탐색 가능.4. 6알 이상 연속적으로 놓였을 경우 무효
: 한 방향으로 5알이 놓여져 있는 경우 그 반대 뱡향에 돌이 놓인 경우도 생각하여야 한다. 이 문제의 함정이라고 생각하는 부분이며, 본인도 이 함정에 호되게 당했다.5. 동시에 이기거나 2번 이상의 승리의 경우는 없음
: 예외의 경우는 없으므로 마음 편하게 승리한 바둑알만 잘 찾자.
2. 테스트 케이스 분석
입력
1. 입력시 검은 바둑알 1, 흰 바둑알 2, 놓이지 않은 곳은 0
2. 숫자는 한 칸씩 띄어서 표시(공백 존재)출력
1. 이긴 돌의 숫자를 출력(검은 바둑알 1, 흰 바둑알 2)
2. 세로로 5알을 만들어서 승리한 경우 상단 바둑알의 좌표, 그렇지 않은 경우 제일 좌측의 바둑알 좌표를 그 다음줄에 공백을 두고 가로줄 번호 세로줄 번호로 출력 -> 해당 부분은 문제를 풀기 위한 힌트를 알려주는 부분이다. 4, 8방 등 n방 순회를 하는 경우 쓸모없는 부분을 탐색하지 않기 위해 방향구분자 설정에 고민을 한다. 배열을 좌측 상단에서 우측하단으로 순차적으로 완전탐색을 할 때 첫번째로 유색돌(백 또는 흑돌)을 만나는 지점에서 ↗,→,↘,↓ 4방을 탐색하는 경우여야만 해당 출력값을 쉽게 도출할 수 있다. 이 부분에서 본인은 순회탐색 방향자의 힌트를 얻었다. + 바둑판은 19x19이지만 21x21로 초기화하여 상단,하단,양측 값은 그저 경계값으로 활용할 경우 좌표 출력값으로 배열 인덱스 +1을 하지 않아도 되므로 Padding 잡기술을 활용하면 더욱 더 쉬울 것이라는 힌트를 주었지만 본인이 실전 문제를 풀때는 익숙치 않아서 활용하지 못했다.
2. 승부가 나지 않았을 경우 0 출력
3. 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Boj_2615 {
//순회탐색용 방향구분자(특정 인덱스 기준 ↗,→,↘,↓,↙,←,↖,↑을 나타냄)
private static int[] dr = {-1, 0, 1, 1, 1, 0, -1, -1};
private static int[] dc = {1, 1, 1, 0, -1, -1, -1, 0};
//바둑판을 의미하는 2차원 배열
private static String[][] go = new String[19][19];
//연속된 바둑알을 세기 위한 counter
private static int counter;
//승리자 유무 체크용i ndex -> 0또는 1이어서 굳이 int형이 아닌 boolean형으로 처리 가능
private static int index = 0;
public static void main(String[] args) throws IOException {
// 입력 부분
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 19; i++) {
go[i] = br.readLine().split(" ");
}
///////////////////////////// 로직 부분////////////////////////////
bkfor : for (int i = 0; i < go.length; i++) {
for (int j = 0; j < go.length; j++) { // 좌측상단에서 우측하단으로 완전탐색
//흑돌 또는 백돌 탐지 시
if(go[i][j].equals("1") || go[i][j].equals("2")) {
// ↗,→,↘,↓방향 탐지시작
for (int k= 0; k < 4; k++) {
// 흑돌 또는 백돌 한 번 세주고 시작
counter=1;
// 5알이 연속으로 놓여져 있을 시 && 오목이라면 그 정반대 방향 탐색(6목이상 여부 확인)
if(check(k, go[i][j], i, j)==5 && !checkPrev(k+4 ,go[i][j], i, j)) {
//출력 기준대로 출력(배열 인덱스 + 1씩)
System.out.printf("%s\n%d %d", go[i][j], i+1, j+1);
index = 1; // 승리한 돌 존재 표시
break bkfor; // 중첩 for문 탈출(완전탐색 종료)
}
}
}
}
}
//승리한 플레이어 없음
if(index !=1) {
System.out.println(0);
}
}
//////////////////////////////////////메서드 부분/////////////////////////////
// 특정 바둑알 기준 특정 방향으로 5알 연속 바둑알 존재시 반대방향 탐지용(6목 이상 여부) 메서드
private static boolean checkPrev(int k, String player, int r, int c) {
//바둑판 경계를 넘지 않으며 && 파라미터로 받은 방향(↙,←,↖,↑ 중 1)에 바둑알이 존재한다면 True->즉 6목 이상
return 0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player);
}
// 특정 방향 구분자, 돌의 색깔, 탐색 시작 지점을 파라미터로 받음
private static int check(int k, String player , int r, int c) {
if(k == 0) { //↗방향 탐색 (k==1 or 2, or 3일 때 같은 로직)
//바둑판 밖을 탐색하는 경우가 아니고, 해당 방향에 같은 색의 바둑돌이 존재한다면
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++; // 연속된 바둑알 수 ++
check(k, player, r+dr[k], c+dc[k]); //해당 방향 계속 탐색
} else {
// 바둑판 밖을 탐색하는 경우거나, 해당 방향에 바둑돌이 존재하지 않는 경우 셋던 바둑알 수 return
return counter;
}
} else if (k == 1) {//→방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
}else if (k == 2) {//↘방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
} else if (k == 3) {//↘방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
}
return counter;
}
}부분 대체 가능한 코드 (재귀메서드 -> for문)
// 특정 방향 구분자, 돌의 색깔, 탐색 시작 지점을 파라미터로 받음
private static int check(int k, String player , int r, int c) {
if(k == 0) { //↗방향 탐색 (k==1 or 2, or 3일 때 같은 로직)
//바둑판 밖을 탐색하는 경우가 아니고, 해당 방향에 같은 색의 바둑돌이 존재한다면
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++; // 연속된 바둑알 수 ++
check(k, player, r+dr[k], c+dc[k]); //해당 방향 계속 탐색
} else {
// 바둑판 밖을 탐색하는 경우거나, 해당 방향에 바둑돌이 존재하지 않는 경우 셋던 바둑알 수 return
return counter;
}
} else if (k == 1) {//→방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
}else if (k == 2) {//↘방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
} else if (k == 3) {//↘방향 탐색
if (0<=r+dr[k] && r+dr[k] < 19 && 0<=c+dc[k] && c+dc[k] < 19 && go[r+dr[k]][c+dc[k]].equals(player)) {
counter++;
check(k, player, r+dr[k], c+dc[k]);
} else {
return counter;
}
}
return counter;
}
}해당 재귀 메서드는 for문으로 표현하면 중복을 제거할 수 있다.
private static int check(int k, String player , int r, int c) {
int counter = 1;
int nr = r+dr[k], nc= c+dc[k];
for(; 0<=nr && nr < 19 && 0<=nc && nc < 19 && go[nr][nc].equals(player);) {
counter++;
nr += dr[k];
nc += dc[k];
}
return counter;
}4. 숙지할 내용
- 항상 경계값을 벗어나는 지 체크할 것, 경계값 처리 하기 번거로울 경우 padding 잡기술 활용 (19x19 -> 21x21배열 선언 후 경계값을 관련 없는 값으로 초기화)
- 탐색 시 이미 지나가 버린 데이터가 유의미한 경우 유의미한 데이터 추가 탐색 필요한 지 생각하기.
- 테스트케이스가 맞았다고 소스코드가 맞은 것은 아니므로 예외 상황 고려해서 테스트 케이스 입력해보기
- 재귀는 for문으로, for문은 재귀메서드로 표현할 수 있다.
