[백준] 2615번 - 오목 java

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

 

난이도 : S1

Tag : Simulation

풀이 일자 : 2025-03-13

---

문제 탐색하기

• 이기는 경우: 같은 색의 바둑알이 정확히 5개 연속으로 놓인 경우 (가로, 세로, 대각선)
• 6개 이상 연속될 경우 승리로 인정되지 않음
• 바둑알 정보
  • 검은 바둑알: 1
  • 흰 바둑알: 2
  • 빈자리: 0
• 출력 조건
  • 검은색이 이긴 경우 1 출력
  • 흰색이 이긴 경우 2 출력
  • 승부가 결정되지 않은 경우 0 출력
  • 이겼을 경우 → 연속된 다섯 개의 바둑알 중 가장 왼쪽에 위치한 바둑알의 좌표 출력
    • 세로로 배치된 경우 → 가장 위쪽의 바둑알 좌표 출력

입력값

• 19×19 크기의 바둑판 상태

즉 이 문제는 바둑판을 탐색하며 오목(정확히 5개 연속)을 찾고, 가장 왼쪽 또는 위쪽에 있는 바둑알의 위치를 정확하게 출력하는 것이 중요합니다.

가능한 시간복잡도

이 문제는 완전탐색으로 풀 수 있습니다.

각 바둑판의 모든 위치에서 연속된 바둑알이 정확히 5개인지 확인해야 합니다.

 

이를 위해 dx, dy 테크닉을 활용하여 4가지 방향(→, ↓, ↘, ↗)으로 탐색합니다.

또한, 6개 이상 연속되는 경우를 방지하기 위해 역순 탐색을 한 번 더 진행하여 정확히 5개만 포함되었는지 확인합니다.

 

시간 복잡도를 계산해 보면:

• 예상 시간복잡도는 바둑판 크기가 19*19이므로 각 바둑판 위치를 탐색하는 O(19*19) = O(361)
• 각 칸별로 최대 4가지 방향을 탐색하므로 O(4)
• 각 방향에서 바둑알이 끊길 때까지 연속 탐색 O(18) 
• 역방향도 탐색하므로 O(18+18) 총 36번

최악의 경우 O(361 ×4 ×36)=O(52056)의 시간 복잡도가 걸리게 됩니다.

이는 1억 번의 연산 안에 들어오므로 충분히 안정적인 풀이가 가능합니다.

알고리즘 선택

이 문제는 완전탐색을 사용하여 풀어보겠습니다.

완전탐색을 선택한 이유는 모든 바둑알의 위치를 하나씩 확인하면서 연속된 5개의 바둑알이 존재하는지 탐색하면 되기 때문입니다.

특정한 자료구조나 복잡한 알고리즘이 필요하지 않고, 단순한 탐색만으로 해결할 수 있습니다.

 

탐색할 방향이 가로(→), 세로(↓), 우하향(↘), 우상향(↗) 4가지로 한정적이기 때문에 모든 방향을 확인하는 것이 어렵지 않습니다.

각 방향으로 탐색하면서 연속된 바둑알 개수를 세고, 정확히 5개일 때만 승리로 인정하면 됩니다.

 

또한, 바둑판 크기가 19 ×19(총 361칸)로 크지 않아 완전탐색을 적용해도 충분히 해결 가능합니다.

탐색 중간에 바둑알이 끊기면 조기 종료되므로, 실제 연산량은 최악의 경우보다 훨씬 적습니다.

---

코드 설계하기

1. 값을 입력받아 2차원 배열에 저장
2. 모든 좌표에서 4가지 방향 탐색
   • 연속된 바둑알 개수를 카운트
   • 역방향도 탐색하여 정확히 5개인지 확인
   • 가장 왼쪽 바둑알 좌표를 기록
3. 정확히 5개라면 해당 좌표를 출력하고 종료
4. 승부가 나지 않았다면 0 출력

회차 별 수정 사항

1회 차 :

디버깅용으로 적어둔 코드를 제거하지 않아 오답처리 되었다.

System.out.println(cnt); //연속적인 바둑돌의 개수

2회 차:

최대 바둑판의 크기를 17로 하는 실수를 발겼했다.

19로 수정했지만, 여전히 풀리지 않았다.

수정 전

public static final int MAX_SIZE = 17;

 

수정 후

public static final int MAX_SIZE = 19;

3회 차:

실패 원인을 찾다가 특정 반례에서 좌표를 반환할 때 가장 왼쪽좌표를 반환하지 않는다는 걸 알게 되었다.

그래서 startX와 startY를 추가하여 탐색 시 가장 왼쪽 좌표를 저장하는 로직을 추가하였다.

또한, 기존코드는 boolean값을 반환하여 승패여부만 확인했지만, 이를 int[] 형태의 반환으로 바꾸어 정확한 좌표를 반환하도록 했다.

 

처음 반환 방식

public static boolean Check_go(int y, int x) {
    int[] dy = {1,0,1,-1};
    int[] dx = {0,1,1,1};
    int stone = go[y][x];

    for(int i=0; i<4; i++){
        int cnt = 1;
        int ny = y;
        int nx = x;
        
        while(true){
            ny+=dy[i];
            nx+=dx[i];
            
            if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
            if(go[ny][nx] != stone) break;
            cnt++;
        }

        ny = y;
        nx = x;
        while(true){
            ny-=dy[i];
            nx-=dx[i];

            if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
            if(go[ny][nx] != stone) break;
            cnt++;
        }

        if (cnt == 5) return true;
    }
    return false;
}

 

수정된 방식

public static int[] Check_go(int y, int x) {
    int[] dy = {1,0,1,-1};
    int[] dx = {0,1,1,1};
    int stone = go[y][x];

    for(int i=0; i<4; i++){
        int cnt = 1;
        int ny = y;
        int nx = x;
        int startY = y, startX = x;
        
        while(true){
            ny+=dy[i];
            nx+=dx[i];
            
            if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
            if(go[ny][nx] != stone) break;
            cnt++;

            if (nx < startX || (nx == startX && ny < startY)) {
                startX = nx;
                startY = ny;
            }
        }

        ny = y;
        nx = x;
        while(true){
            ny-=dy[i];
            nx-=dx[i];

            if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
            if(go[ny][nx] != stone) break;
            cnt++;

            if (nx < startX || (nx == startX && ny < startY)) {
                startX = nx;
                startY = ny;
            }
        }

        if (cnt == 5) {
            return new int[]{startY + 1, startX + 1};
        }
    }
    return null;
}

---

 

정답코드

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

class Main {
    public static final int MAX_SIZE = 19;
    public static int[][] go = new int[MAX_SIZE][MAX_SIZE];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0; i<MAX_SIZE; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<MAX_SIZE; j++){
                go[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < MAX_SIZE; i++) {
            for (int j = 0; j < MAX_SIZE; j++) {
                if (go[i][j] == 0) continue;
                int[] result = Check_go(i, j);
                if (result != null) {
                    System.out.println(go[i][j]);
                    System.out.println(result[0] + " " + result[1]);
                    return;
                }
            }
        }
        System.out.println(0);
    }

    public static int[] Check_go(int y, int x) {
        int[] dy = {1,0,1,-1};
        int[] dx = {0,1,1,1};
        int stone = go[y][x];

        for(int i=0; i<4; i++){
            int cnt = 1;
            int ny = y;
            int nx = x;
            int startY = y, startX = x;
            
            while(true){
                ny+=dy[i];
                nx+=dx[i];
                
                if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
                if(go[ny][nx] != stone) break;
                cnt++;

                if (nx < startX || (nx == startX && ny < startY)) {
                    startX = nx;
                    startY = ny;
                }
            }

            ny = y;
            nx = x;
            while(true){
                ny-=dy[i];
                nx-=dx[i];

                if(ny >= MAX_SIZE || nx >= MAX_SIZE || ny < 0 || nx < 0) break;
                if(go[ny][nx] != stone) break;
                cnt++;

                if (nx < startX || (nx == startX && ny < startY)) {
                    startX = nx;
                    startY = ny;
                }
            }

            if (cnt == 5) {
                return new int[]{startY + 1, startX + 1};
            }
        }
        return null;
    }
}