자료구조&알고리즘/백준
[JAVA] 2615번 - 오목
celinayk
2024. 9. 19. 22:19
반응형
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
처음에는 DFS/BFS로 접근해야하나 생각했다
1이 연속으로 5개가 있어야하니까 그래프탐색을 통해 탐색하면 된다 생각했다.
하지만 그렇게 풀 수 없다.
연속으로다섯개가 0 0 0 0 0 이렇게 있어도 다른 오목이 또 붙어있을수도 있기 때문이다
0 0 0 0 0 이런식으로 되어있을 수도 있기 때문에 그래프탐색은 불가능이다.
0
직접 구현을 해서 확인해야한다.
5줄이 되어 정답이 될 수 있는 경우를 4개로 나눠서 해당하는지 보면된다.
- 1. 가로로 5줄인지
- 2. 세로로 5줄인지
- 3. 오른쪽 위로 대각선 5줄인지
- 4. 오른쪽 밑으로 대각선 5줄인지
각 4가지 경우를 코드로 표현하면 이렇다.
- 1. i는 그대로이고 j가 1씩증가한다
- 2. i가 1씩증가하고 j는 그대로
- 3. i가 1씩증가하고 j는 1씩 줄어든다
- 4. i와 j 둘다 1씩 증가한다.
코드의 과정은 이렇다.
1. 바둑판 입력
바둑판의 숫자들을 입력받는다.
2. 5오목인지 확인하는 함수
연속된 5개의 바둑알이 있는지 확인하는 함수, 배열타입으로 반환
1. 돌이 있으면
2. 가로,세로,오른쪽아래대각선,오른쪽위대각선 각각 연속된 5개의 돌이 있는지 확인(방향체크함수)
3. 연속된 5개의 돌을 찾으면 해당 돌의 색깔, 가장 왼쪽/위쪽 좌표 배열을 반환
4. 5개 연속 못찾으면 0 반환
이렇게 각 방향마다 방향체크함수를 불러서 검사를 한다. 이때 0,1은 가로,세로각각 이동하는 양이다
//가로 검사
if(checkDirection(arr,i,j,0,1,color)) {
return new int[]{color, i + 1, j + 1};
}
//세로 검사
else if(checkDirection(arr,i,j,1,0,color)) {
return new int[]{color, i + 1, j + 1};
}
// 오른쪽 밑으로 내려가는 대각선 검사
else if(checkDirection(arr,i,j,1,1,color)) {
return new int[]{color, i + 1, j + 1};
}
// 오른쪽 위로 올라가는 대각선 검사
else if(checkDirection(arr,i,j,1,-1,color)) {
return new int[]{color, i + 5, j -3};
}
3. 방향체크 함수
4가지 방향을 검사한다.
파라미터로 현재 x,y좌표, 움직이는만큼 dx,dy양, 색을 입력받는다.
- 가로 방향 (dx = 0, dy = 1): 오른쪽으로 이동.
- 세로 방향 (dx = 1, dy = 0): 아래로 이동.
- 오른쪽 아래 대각선 (dx = 1, dy = 1): 오른쪽 아래로 이동.
- 오른쪽 위 대각선 (dx = 1, dy = -1): 오른쪽 위로 이동.
현재 좌표를 기준으로 주어진방향으로 5개의 연속된 돌이 있는지확인한다.
for문을 5번 돌면 예를 들어 (1,2)에서 가로 방향 탐색이라면 입력받은 (0,1)씩 이동하게된다
i가 1부터 5까지니까 5개연속으로 이동하는지 알 수 있다.
for(int i=1; i<=5; i++) {
int nx = x + dx *i;
int ny = y + dy * i;
if (nx >= 0 && nx < 19 && ny >= 0 && ny < 19 && arr[nx][ny] == color) {
cnt++;
} else {
break;
}
}
그리고 6목인지 확인해야한다
처음 좌표의 이전, 마지막5번째 좌표의 이후를 확인하면 된다
int prevX = x - dx;
int prevY = y - dy;
int nextX = x + dx * 5;
int nextY = y + dy * 5;5개의돌이고 6목이 아니라면 true를 반환한다.
시간복잡도
바둑판이 19*19이니까 O(19 × 19), 즉 **O(361)**이다
1초안에 충분히 가능!
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1.바둑판 입력받기
2. 5오목 찾기
3. 각 방향함수로 탐색해서 찾는다
4. 출력
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int [][] arr = new int[19][19];
// 바둑판 입력 받기
for(int i=0; i<19; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<19; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int[] result = checkOmok(arr);
// 결과 출력
if (result[0] == 0) {
System.out.println(0); // 승리자 없으면 0 출력
} else {
System.out.println(result[0]); // 승리한 돌의 색 출력
System.out.println(result[1] + " " + result[2]); // 가장 왼쪽 또는 위쪽 돌의 좌표 출력
}
}
private static int[] checkOmok(int[][] arr) {
for(int i=0; i<19; i++) {
for(int j=0; j<19; j++) {
if(arr[i][j] != 0) {
int color = arr[i][j];
//가로 검사
if(checkDirection(arr,i,j,0,1,color)) {
return new int[]{color, i + 1, j + 1};
}
//세로 검사
else if(checkDirection(arr,i,j,1,0,color)) {
return new int[]{color, i + 1, j + 1};
}
// 오른쪽 밑으로 내려가는 대각선 검사
else if(checkDirection(arr,i,j,1,1,color)) {
return new int[]{color, i + 1, j + 1};
}
// 오른쪽 위로 올라가는 대각선 검사
else if(checkDirection(arr,i,j,1,-1,color)) {
return new int[]{color, i + 5, j -3};
}
}
}
}
return new int[]{0, 0, 0};
}
private static boolean checkDirection(int[][] arr, int x, int y, int dx, int dy, int color) {
int cnt = 1;
for(int i=1; i<=5; i++) {
int nx = x + dx *i;
int ny = y + dy * i;
if (nx >= 0 && nx < 19 && ny >= 0 && ny < 19 && arr[nx][ny] == color) {
cnt++;
} else {
break;
}
}
if(cnt==5) {
// 앞과 뒤에 같은 색 돌이 있으면 안 됨
int prevX = x - dx;
int prevY = y - dy;
int nextX = x + dx * 5;
int nextY = y + dy * 5;
if ((prevX < 0 || prevX >= 19 || prevY < 0 || prevY >= 19 || arr[prevX][prevY] != color) &&
(nextX < 0 || nextX >= 19 || nextY < 0 || nextY >= 19 || arr[nextX][nextY] != color)) {
return true;
}
}
return false;
}
}