이 문제는 모든 경우를 탐색하면 간단히 풀 수 있는 문제입니다.
BOJ 2615번 오목 문제 자바(java) 풀이
- 랭크 : 실버3(solved.ac)
- 백준 온라인 저지(BOJ) 2615번 오목 문제 자바 풀이
- 백준 2615 오목
문제 간단 정리
- 알이 연속으로 5개 이상 놓여있으면 이기게 된다(가로, 세로, 대각선 모두)
- 바둑판 상태가 주어졌을때 어떤 알이 이겼는지, 승부가 안됬는지 판단하여라.
어떻게 보면 쉬워보이지만 아래 사항을 간과하여 틀리는 분들이 많습니다.
단 여섯알 이상 놓인 경우는 이긴 것이 아닌다
바둑알 상태
- 0: 놓이지 않음
- 1: 검은 바둑알
- 2: 흰 바둑알
문제풀이
이 문제는 19 * 19의 map을 탐색하는 문제이다. 그래서 그냥 모든 경우를 따져 주면된다.
bfs나 dfs 이런 걸 적용할 필요 없이 단순 하게 생각하여 풀어야 해요
그렇지 않으면 오히려 산으로 갈 수 도 있답니다!!
그리고 방법은 여러가지가 있을 수 있다.
- 왼쪽 위 부터 탐색한다고 하면 탐색해야할 방향은 다음과 같다.
- 가로(→)
- 세로(↓)
- 오른쪽 아래 대각선(↘)
- 오른쪽 위 대각선(↗)
이겼을 경우 가장 왼쪽 알을 출력해야하기 때문에 대각선 방향을 다음과 같이 선택하였습니다.
-
이렇게 탐색하여 5개의 알이 있다면 탐색 기준점 뒤의 알과 끝쪽에 알이 더 있는지 확인한다. (육목 칠목 등을 확인하기 위해서)
-
탐색하다가 오목이 맞다면 승리한 알의 색과 좌표를 출력하고 종료한다.
물론 훨씬 코드를 훨씬 간단히 작성할 수 있다.
하지만 실제 시험이라 생각하고 모든 경우를 따져 naive하게 코드를 작성하였다.
코드는 아래 첨부하였습니다
주석도 같이 달았으니 참고하시고 이해 안가시는 부분이 있다면 댓글 남겨주세요!!
백준 오목 자바 코드 github도 첨부합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
static int[][] map;
static int cnt = 0, row = 1, col = 1;
static int ur=1, dr=1;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1: 검은 바둑알
// 2: 흰 바둑알
// 0: 알이 놓이지 않음
map = new int[20][20];
for(int i=1; i<=19; i++){
String[] temp = br.readLine().split(" ");
for(int j=1; j<=19; j++){
map[i][j] = Integer.parseInt(temp[j-1]);
}
}
// 어떤 색이 이겼는가?? 승부가 나지 않았는가?
// 5개의 알이 연속으로 가로, 세로, 대각선으로 놓인 경우에 이김
// 6개는 이긴게 아니다.
// 가로로 이긴 경우 가장 왼쪽알
// 대각선이나 세로는 가장 위 왼쪽
for(int i=1; i<=19; i++){
for(int j=1; j<=19; j++){
if(map[i][j] == 1){
search(i,j,1);
}
else if(map[i][j] == 2){
search(i,j,2);
}
}
}
System.out.println("0");
br.close();
}
public static boolean check(int x, int y, int num){
if(isValidPosition(x, y)){
if(map[x][y] != num){
return false;
}
}
else
return false;
return true;
}
public static boolean isValidPosition(int x, int y){
if(x < 1 || x > 19 || y < 1 || y > 19)
return false;
return true;
}
public static void search(int i, int j, int num){
// 가로에 대해서 확인
for(int k=1; k<5; k++){
if(!check(i,j+k, num))
break;
else
row++;
}
// 세로 검사
for(int k=1; k<5; k++){
if(!check(i+k, j, num))
break;
else
col++;
}
// 아래 오른쪽로 대각선 검사
for(int k=1; k<5; k++){
if(!check(i+k, j+k, num))
break;
else
dr++;
}
// 위로 오른쪽 대각선
for(int k=1; k<5; k++){
if(!check(i-k, j+k, num))
break;
else
ur++;
}
// 양 쪽 끝으로 더 연결된 것이 있는지 확인
if(row == 5){
if(isValidPosition(i, j-1)){
if(map[i][j-1] != num) {
if(isValidPosition(i, j+5)){
if(map[i][j+5] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
else {
if(isValidPosition(i, j+5)){
if(map[i][j+5] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
if(col == 5){
if(isValidPosition(i-1, j)){
if(map[i-1][j] != num) {
if(isValidPosition(i+5, j)){
if(map[i+5][j] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
else {
if(isValidPosition(i+5, j)){
if(map[i+5][j] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
if(dr == 5){
if(isValidPosition(i-1, j-1)){
if(map[i-1][j-1] != num) {
if(isValidPosition(i+5, j+5)){
if(map[i+5][j+5] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
else {
if(isValidPosition(i+5, j+5)){
if(map[i+5][j+5] != num)
finish(i,j,num);
}
else
finish(i,j,num);
}
}
if(ur == 5){
if(isValidPosition(i+1, j-1)){
if(map[i+1][j-1] != num) {
if(isValidPosition(i-5, j+5)){
if(map[i-5][j+5] != num) {
finish(i,j,num);
}
}
else
finish(i,j,num);
}
}
else {
if(isValidPosition(i-5, j+5)){
if(map[i-5][j+5] != num) {
finish(i,j,num);
}
}
else
finish(i,j,num);
}
}
row = 1;
col = 1;
ur = 1;
dr = 1;
}
public static void finish(int i, int j, int num) {
System.out.println(num);
System.out.println(i + " " + j);
System.exit(0);
}
}