[코드트리/NOVICE MID] 오목 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 1, 1, 1};   // 가로 세로 왼쪽대각선 오른쪽대각선 
    static int[] dy = {1, 0, 1, -1};
 
    static int[][] grid = new int[19][19];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 입력받기
        for(int i = 0 ; i < 19 ; i++) {
            String[] str = br.readLine().split(" ");
            for(int j = 0 ; j < 19 ; j++) {
                grid[i][j] = Integer.parseInt(str[j]);
            }
        }
 
        for(int i = 0 ; i < 19 ; i++) {
            for(int j = 0 ; j < 19 ; j++) {
                if(grid[i][j] != 0) {
                    for(int d = 0 ; d < 4 ; d++) {
                        int nx = i;
                        int ny = j;
                        int cnt = 1;    // 일치하는 바둑알 개수
 
                        // 증가하는 방향 탐색
                        while(true) {
                            nx += dx[d];
                            ny += dy[d];
 
                            if(inRange(nx, ny) && grid[i][j] == grid[nx][ny])   cnt++;
                            else    break;
                        }
 
                        // 증가하는 방향의 "반대 방향" 탐색
                        nx = i;
                        ny = j;
 
                        while(true) {  // 💥
                            nx -= dx[d];
                            ny -= dy[d];
 
                            if(inRange(nx, ny) && grid[i][j] == grid[nx][ny])   cnt++;
                            else  break;
                        }
 
                        // 같은 오목눈이 5개라면
                        if(cnt == 5) {
                            System.out.println(grid[i][j]);
                            System.out.println((i + 2 * dx[d] + 1) + " " + (j + 2 * dy[d] + 1)); // 오목일 때의 중간값
                            return;
                        }
                    }
 
                }
            }
        }
 
        // 아무도 이기지 않았을 경우
        System.out.println(0);
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < 19 && 0 <= y && y < 19);
    }
}
 

 

 

 

🧩  해결 아이디어

• 완전탐색 + dx dy technique

- 각 칸마다 가로, 세로, 대각선으로 인접한 8개 칸에 대해 같은 종류의 바둑돌인지 확인

- 종류가 같고, 한 방향으로 같은 숫자가 5개 나온다면, 그 때 문제에서 원하는 값을 출력하도록 한다. (Line 51- 54)

 

 

 

💥 유의사항

📌 대각선 방향 탐색

- 왼쪽 아래, 아래쪽, 오른쪽 아래 순서로 탐색

 

🕵️‍♀️ while(true) 하는 이유

: 연속으로 일치하는 바둑알 갯수를 나타내는 변수 cnt가 5가 되지 않는 경우에도, 해당 방향으로 계속 탐색을 진행하기 위함

 

 

---

🔺 다른 풀이들

- 8방향 탐색을 활용하셨다. 이 틀을 잊지 말자....

import java.util.Scanner;
 
public class Main {
    public static final int DIR_NUM = 8;
    
    public static int[][] arr = new int[19][19];
    
    public static int[] dx = new int[]{1, 1, 1, -1, -1, -1, 0, 0};    // 8방향 탐색
    public static int[] dy = new int[]{-1, 0, 1, -1, 0, 1, -1, 1};
    
    public static boolean inRange(int x, int y) {
        return 0 <= x && x < 19 && 0 <= y && y < 19;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < 19; i++)
            for(int j = 0; j < 19; j++)
                arr[i][j] = sc.nextInt();
        
 
        for(int i = 0; i < 19; i++) {
            for(int j = 0; j < 19; j++) {
                if(arr[i][j] == 0) continue;
                
                for(int k = 0; k < DIR_NUM; k++) // 8방향 탐색
                    int cnt = 1;
                    int curx = i;
                    int cury = j;
 
                    while(true) {
                        int nx = curx + dx[k];
                        int ny = cury + dy[k];
 
                        if(!inRange(nx, ny))    break;
                        if(arr[nx][ny] != arr[i][j])    break;
 
                       cnt++;
                        curx = nx;
                        cury = ny;
                    }
 
                    if(cnt== 5) {
                        System.out.println(arr[i][j]);
                        System.out.print((i + 2 * dx[k] + 1) + " " + (j + 2 * dy[k] + 1)); // 오목일 때의 중간값
                        System.exit(0);
                    }
                }
            }
        }
 
        // 어느 것도 오목이 아닌 경우
        System.out.print(0);
    }
}

 

 

---

💬 느낀 점

대각선 처리를 어찌하지... 각 점에서 어떻게 하지..하다가 시간을 굉장히 많이 써버렸다.

다음엔 아이디어를 빨리 생각해내서 구현하는 시간도 줄이고 빠르게 풀도록....

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

(Java/자바) - 백준(BOJ) 2615번 : 오목