[완전탐색][Java][BOJ] #2615. 오목

#완전탐색  #Silver1

https://www.acmicpc.net/problem/2615

🌷 문제 설명

✏️ 백준 연습문제: #2615. 오목
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.


⌨️ 입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

🖨️ 출력
첫줄에 검은색이 이겼을 경우에는 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 0	1 3 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 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 1 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 2 2 2 2 2 2	0

 

💡 해결 포인트

1.  6개 돌이 연속으로 놓인 경우는 이긴 것이 아니다 
- 따라서 i, j 이전 돌 체크 필요
- 여기서 이전 돌이란, 연속으로 놓인 5개의 돌 중 첫번째 돌의 이전 돌을 말함.

2. break와 return의 차이
- break는 현재 포함된 반복문만 종료하고
- return의 경우 함수 자체를 종료시킨다

 

🌷 내 코드

1. 완전탐색

import java.io.*;
import java.util.*;

public class BOJ_2615 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 바둑판 받기
    int[][] map = new int[19][19];

    for (int i = 0; i < 19; i++) {
      String[] line = br.readLine().split(" ");
      for (int j = 0; j < 19; j++) {
        map[i][j] = Integer.parseInt(line[j]);
      }
    }

    // 방향
    int[] dx = {1, 1, 0, -1}; 
    int[] dy = {0, 1, 1, 1};

    // 검사
    // 참고로 검은색 1, 흰색 2
    for (int i = 0; i < 19; i++) {
      for (int j = 0; j < 19; j++) {
        if (map[i][j] == 0) continue; // 돌이 없으면 넘어가기

        int stoneColor = map[i][j]; // 돌의 색 // answer

        // 돌을 찾으면 상하좌우 체크
        for (int k = 0; k < 4; k++) { // 4 방향 체크
          int cnt = 1; // 연속된 돌의 개수 저장
          int x = i; // 현재 x
          int y = j; // 현재 y

          while (true) { // 쭉 확인
            x += dx[k]; // x 이동 // dx={1, 1, 0, -1}
            y += dy[k]; // y 이동 // dy={0, 1, 1, 1}

            // 바둑판을 벗어나지 않고, 같은 색의 돌이면
            if (x >= 0 && x < 19 && y >= 0 && y < 19 && map[x][y] == map[i][j]) { 
              cnt++; // 돌의 개수 증가
            } else { // 바둑판을 벗어나거나, 다른 색의 돌이면
              break; // 다음 연속된 돌 찾으러 가기
            }
          }

          // 5개의 돌이 연속되어 있으면
          if (cnt == 5) {

            int px = i - dx[k]; // 이전 x
            int py = j - dy[k]; // 이전 y

            // 6번째 돌이 같은 색이면(6목 방지)
            if (px >= 0 && px < 19 && py >= 0 && py < 19 && map[px][py] == map[i][j]) {
              continue;
            }

            System.out.println(stoneColor); // 돌의 색 출력
            System.out.println((i + 1) + " " + (j + 1)); // 돌의 위치 출력
            return; // 종료
          }
          
            
          }
        } 
        }
        System.out.println(0); // 오목 없으면 0 출력
      }
    }

 

🌷 코멘트

뭔가 접근은 적당히 맞는 방향으로 했는데 구현을 못해서ㅋㅋ 힘들었다
6목 조건은 진짜 생각도 못함.. 질문게시판에서 반례 하나 찾아와서 돌리면서 알게됐다. 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com