白準2615 java-解凹問題

1.問題分析

質問する
1.碁盤は19×19
:2 D配列を考慮できます.また,配列に入る要素は0,1,2のみであるため,整数型やString型,Char型など便利な方法で配列宣言を行うことができる.
さらに探求する必要がある場合は、paddingという名前のコンパクトテクノロジー(必要な配列のインデックス長よりも長いタグ境界値を作成する方法)によって境界値を超えるかどうかを処理することができるので、padding-(このプールには充填が使用されていません.)
2.黒と白のプレイヤーが存在する
:問題は黒1、白2、PASSと決めました
3.5粒連続勝利
:同じ論理のナビゲーションが必要な場合は、再帰を使用します.また,同じ石を1方向に5回連続して置くことを確保するためには,再帰法の他にcount変数をStatic訪問者として用いることもできる.
「貴内にある条件」
1.他の色の石(1の場合は2、2の場合は1)に遭遇した場合、戻り戻り戻り戻りはcount値を返し、
2.碁盤境界に遭遇したときに再帰終了count値を返し、
3.ある方向をナビゲートするには、ある方向の値を知る必要があります.
4.連続放置6粒以上無効
:一つの方向に5粒置いてある場合は、石が別の方向に置かれている場合も考えられます.この問題の落とし穴だと思った部分も、本人はこの落とし穴にひどく穴をあけられた.
5.同時に勝ったり2回以上勝ったりしていない場合
:例外はありませんから、心の安らぎの駒を見つければいいのです.

2.テストケーススタディ

入力
1.入力時に黒の駒1、白の駒2、置かない場所は0
2.数字はスペースで区切られて表示されます(スペースは存在します)
しゅつりょく
1.長石頭の数字を出力する(黒駒1、白駒2)
2.縦に5つの駒を打って勝つ場合は、上端の駒の座標である.そうでなければ、第1左側の駒座標の次の行に空白を残し、横線番号縦線番号で出力する->この部分は問題解きを促す部分である.4,8などn方巡視を行う場合,不要な部分を探索しないために方向区切り記号を設けることが考えられる.左上から右下へ順番に並べて完全探索を行うと,有色石(白または黒の石)に最初に遭遇した場所でのみ探索↔,→,−,↓の4つを探索すると,対応する出力値が容易に得られる.この部分では,本人が巡回探索方向者からヒントを得た.碁盤は19×19ですが、21×21に初期化され、上端、下端、両側の値が境界値のみの場合、座標出力値を配列インデックス+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.おなじみの内容

が常に境界値を超えているかどうかを確認し、境界値の処理が煩雑である場合は、充填コンパクト(19 x->21 x 21アレイ宣言後に境界値を非相関値に初期化)

を使用します.

にナビゲートしたときに古いデータが有意義である場合は、有意義なデータをさらにナビゲートする必要があるかどうかを考慮してください.

入力

テストケースはソースコードが正しいわけではありませんので、例外を考慮してテストケース

を入力してください.

再帰はfor文で表すことができ、for文は再帰方法で表すことができる.

質問リンク:
https://www.acmicpc.net/problem/2615