[백준/JAVA] 2615번: 오목

📖 문제

2615번: 오목

 

 

💡  풀이 방식

• 구현 (브루트포스)

1. 완전탐색으로 모든 지점에서 4방향에 대해 1) 오목이 되었는지, 2) 오목이 되었다면 어떤 색 돌로 오목을 만들었는지, 3)가장 왼쪽에 있는 점은 무엇인지 검은 돌과 흰 돌 좌표에 좌표를 저장하며 진행한다.

 - 가로 방향 확인

 - 세로 방향 확인

 - 대각선1 방향 ( ↘ )확인

 - 대각선2 방향( ↙ )확인

 

2. 값을 입력받은 검은 돌 좌표 리스트와 흰 돌 좌표 리스트를 행 좌표 오름차순으로 정렬한다. (행 좌표가 같으면 열 좌표 기준. 열 좌표 오름차순 기준 정렬해도 될지도)

Collections.sort(bList, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        if(o1[0] != o2[0])
            return o1[0] - o2[0];
        return o1[1] - o2[1];
    }
});

 

 

3. 검은 돌 오목 수 > 흰 돌 오목 수인 경우, 좌표 값으로 검은 돌 좌표 리스트에서 가장 왼쪽 위에 있는 값(= 정렬된 검은 돌 좌표 리스트의 맨 첫 번째 값)을 출력한다.

 

검은 돌 오목 수 < 흰 돌 오목 수인 경우, 좌표 값으로 흰 돌 좌표 리스트에서 가장 왼쪽 위에 있는 값(= 정렬된 흰 돌 좌표 리스트의 맨 첫 번째 값)을 출력한다.

 

검은 돌 오목 수 = 흰 돌 오목 수인 경우, 0을 출력한다.

 

 

 

💥 유의사항

육목이어서는 안 된다.

육목이 발생하는 경우를 방지하고자 해당 점에서부터 육목이 되는 위치의 값 (이전 값, 다음 값)도 함께 확인한다. 이 때 육목 위치의 값이 현재 위치의 값과 같다면 육목이 되므로 하차한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] board;
    
    static List<int[]> bList = new ArrayList<>();   // 검은 돌 좌표 리스트
    static List<int[]> wList = new ArrayList<>();   // 흰 돌 좌표 리스트
    
    static int blackScore, whiteScore;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        board = new int[20][20];        
        for(int i = 1 ; i <= 19 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= 19 ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 1 ; i <= 19 ; i++) {
            for(int j = 1 ; j <= 19 ; j++) {
                if(board[i][j] == 0)    continue;
                
                rCheck(i, j);   // 가로 확인
                cCheck(i, j);   // 세로 확인
                lrCheck(i, j);  // 대각선1 확인
                rlCheck(i, j);  // 대각선2 확인
            }
        }
        
        // 검은 돌과 흰 돌 좌표 리스트, x좌표 기준 오름차순 정렬
        // (x좌표가 같으면, y좌표 기준 오름차순 정렬)
        Collections.sort(bList, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] != o2[0])
                    return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });
        
        Collections.sort(wList, new Comparator<int[]>() {
            @Override 
            public int compare(int[] o1, int[] o2) {
                if(o1[0] != o2[0])
                    return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });
        
        // 승부 결과 출력
        if(blackScore > whiteScore) {
            System.out.println(1);
            System.out.println(bList.get(0)[0] + " " + bList.get(0)[1]);
        }
        else if(blackScore < whiteScore) {
            System.out.println(2);
            System.out.println(wList.get(0)[0] + " " + wList.get(0)[1]);
        }
        else {
            System.out.println(0);
        }
    }
    
    private static void rCheck(int i, int j) {        
        if(board[i][j] == 0 || !inRange(i, j + 4))    return;
        
        if((board[i][j] == board[i][j + 1]) && (board[i][j + 1] == board[i][j + 2]) && (board[i][j + 2] == board[i][j + 3]) && (board[i][j + 3] == board[i][j + 4])) {
            // 오목 갯수가 6개 이상이 되면, 패스
            if(inRange(i, j - 1) && board[i][j] == board[i][j - 1]) return;
            if(inRange(i, j + 5) && board[i][j] == board[i][j + 5]) return;
            
            if(board[i][j] == 1) {
                bList.add(new int[] {i, j});
                blackScore++;
            }
            else if(board[i][j] == 2) {
                wList.add(new int[] {i, j});
                whiteScore++;
            }
        }
    }
    
    private static void cCheck(int i, int j) {        
        if(board[i][j] == 0 || !inRange(i + 4, j))    return;
        
        if((board[i][j] == board[i + 1][j]) && (board[i + 1][j] == board[i + 2][j]) && (board[i + 2][j] == board[i + 3][j]) && (board[i + 3][j] == board[i + 4][j])) {
            // 오목 갯수가 6개 이상이 되면, 패스
            if(inRange(i - 1, j) && board[i][j] == board[i - 1][j]) return;
            if(inRange(i + 5, j) && board[i][j] == board[i + 5][j]) return;
            
            if(board[i][j] == 1) {
                bList.add(new int[] {i, j});
                blackScore++;
            }
            else if(board[i][j] == 2) {
                wList.add(new int[] {i, j});
                whiteScore++;
            }
        }
    }
    
    private static void lrCheck(int i, int j) {        
        if(board[i][j] == 0 || !inRange(i + 4, j + 4))    return;
        
        if((board[i][j] == board[i + 1][j + 1]) && (board[i + 1][j + 1] == board[i + 2][j + 2]) && (board[i + 2][j + 2] == board[i + 3][j + 3]) && (board[i + 3][j + 3] == board[i + 4][j + 4])) {
            // 오목 갯수가 6개 이상이 되면, 패스
            if(inRange(i - 1, j - 1) && board[i][j] == board[i - 1][j - 1]) return;
            if(inRange(i + 5, j + 5) && board[i][j] == board[i + 5][j + 5]) return;
            
            if(board[i][j] == 1) {
                bList.add(new int[] {i, j});
                blackScore++;
            }
            else if(board[i][j] == 2) {
                wList.add(new int[] {i, j});
                whiteScore++;
            }
        }
    }
    
    private static void rlCheck(int i, int j) {        
        if(board[i][j] == 0 || !inRange(i + 4, j - 4))    return;
        
        if((board[i][j] == board[i + 1][j - 1]) && (board[i + 1][j - 1] == board[i + 2][j - 2]) && (board[i + 2][j - 2] == board[i + 3][j - 3]) && (board[i + 3][j - 3] == board[i + 4][j - 4])) {
            // 오목 갯수가 6개 이상이 되면, 패스
            if(inRange(i - 1, j + 1) && board[i][j] == board[i - 1][j + 1]) return;
            if(inRange(i + 5, j - 5) && board[i][j] == board[i + 5][j - 5]) return;
            
            if(board[i][j] == 1) {
                bList.add(new int[] {i + 4, j - 4});
                blackScore++;
            }
            else if(board[i][j] == 2) {
                wList.add(new int[] {i + 4, j - 4});
                whiteScore++;
            }
        }
    }    
    
    private static boolean inRange(int r, int c) {
        return (1 <= r && r <= 19 && 1 <= c && c <= 19);
    }
}
 

 

 

 

➕ 다른 풀이 방식

- dx/dy 활용. 충격받음ㅋㅋ

[ 백준 2615 ] 오목 (Java)

[백준] 오목 2615 [ Java ]

---

💦 어려웠던 점

- 구현 빠르게 하기,,,, 아직 좀 느린 것 같다.

- 육목 조건을 제대로 설정하지 않아 반례를 찾느라 시간이 더 걸렸다..

- ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ아 다른 사람들 조건 보니까 내가 얼마나 무식하게(?) 풀었는지 알았음ㅋㅋㅋㅠ

 

 

🧐 새로 알게 된 내용

- 아 그냥 무작정 무식하게 풀 생각했지 이럴 줄 생각을 하지 못 했다.. 담엔 저렇게 풀어보는 것으로...

 

 

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

 

 

(+240208 2회독)

90분 소요 (16052KB, 152ms)

저번보다 더 무식하게 푼 듯ㅋㅋ

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] board = new int[20][20];
    
    static List<int[]> blackList = new ArrayList<>();
    static List<int[]> whiteList = new ArrayList<>();
    
    static int blackScore, whiteScore, R, C;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        for(int i = 1 ; i <= 19 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= 19 ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                
                if(board[i][j] == 1)         blackList.add(new int[]{i, j});
                else if(board[i][j] == 2)    whiteList.add(new int[] {i, j});
            }
        }
        
        // 검은 돌 오목 확인
        for(int i = 0 ; i < blackList.size() ; i++) {
            int[] now = blackList.get(i);
            
            if(chkGaro(now[0], now[1], 1) == 5) {
                R = now[0];
                C = now[1];
                blackScore++;                
            }
            if(chkSero(now[0], now[1], 1) == 5) {
                R = now[0];
                C = now[1];
                blackScore++;
            }
            if(chkLine1(now[0], now[1], 1) == 5) {  // \
                R = now[0];
                C = now[1];
                blackScore++;                
            }
            if(chkLine2(now[0], now[1], 1) == 5) {  // /
                R = now[0] + 4;
                C = now[1] - 4;
                blackScore++;                
            }
        }
 
        // 흰 돌 오목 확인    
        for(int i = 0 ; i < whiteList.size() ; i++) {
            int[] now = whiteList.get(i);
            
            if(chkGaro(now[0], now[1], 2) == 5) {
                R = now[0];
                C = now[1];
                whiteScore++;                
            }
            if(chkSero(now[0], now[1], 2) == 5) {
                R = now[0];
                C = now[1];
                whiteScore++;
            }
            if(chkLine1(now[0], now[1], 2) == 5) {  // \
                R = now[0];
                C = now[1];
                whiteScore++;                
            }
            if(chkLine2(now[0], now[1], 2) == 5) {  // /
                R = now[0] + 4;
                C = now[1] - 4;
                whiteScore++;                
            }
        }
        
        // 출력하기
        if(blackScore == whiteScore) {
            System.out.println(0);
        }
        else {
            System.out.println(blackScore > whiteScore ? 1 : 2);
            System.out.println(R + " " + C);
        }
    }
    
    // 가로 확인 메서드
    private static int chkGaro(int x, int y, int targetNum) {
        int cnt = 0;
        
        for(int i = y ; i < y + 5 ; i++) {
            if(!inRange(x, i))  return 0;
            if(board[x][i] == targetNum) {
                cnt++;
            }
        }
        
        if(inRange(x, y - 1) && board[x][y - 1] == targetNum)   return 0;
        if(inRange(x, y + 5) && board[x][y + 5] == targetNum)   return 0;
        
        return cnt;
    }
    
    // 세로 확인 메서드
    private static int chkSero(int x, int y, int targetNum) {
        int cnt = 0;
        
        for(int i = x ; i < x + 5 ; i++) {
            if(!inRange(i, y))  return 0;
            if(board[i][y] == targetNum) {
                cnt++;
            }
        }
        
        if(inRange(x - 1, y) && board[x - 1][y] == targetNum)   return 0;
        if(inRange(x + 5, y) && board[x + 5][y] == targetNum)   return 0;
        
        return cnt;
    }
    
    // 대각선1 \ 확인 메서드
    private static int chkLine1(int x, int y, int targetNum) {
        int cnt = 0;
        
        for(int i = 0 ; i < 5 ; i++) {
            if(!inRange(x + i, y + i))  return 0;
            if(board[x + i][y + i] == targetNum)
                cnt++;
        }
        
        if(inRange(x - 1, y - 1) && board[x - 1][y - 1] == targetNum)   return 0;
        if(inRange(x + 5, y + 5) && board[x + 5][y + 5] == targetNum)   return 0;
        
        return cnt;
    }
    
    
    // 대각선2 / 확인 메서드
    private static int chkLine2(int x, int y, int targetNum) {
        int cnt = 0;
        
        for(int i = 0 ; i < 5 ; i++) {
            if(!inRange(x + i, y - i))  return 0;
            if(board[x + i][y - i] == targetNum)
                cnt++;
        }
 
        if(inRange(x - 1, y + 1) && board[x - 1][y + 1] == targetNum)   return 0;
        if(inRange(x + 5, y - 5) && board[x + 5][y - 5] == targetNum)   return 0;
        
        return cnt;
    }
    
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= 19 && 1 <= y && y <= 19);
    }
}
 

 

 

 

---

(참고)

✔ 반례 참고

글 읽기 - [c++] 어떤 부분이 틀린지 잘 모르겠습니다.

글 읽기 - 육목 관련해서 이거 돌려보세요

글 읽기 - 13%에서 틀렸다고 나옵니다. 게시판에 있는 모든 반례 시도 해봤습니