[SWEA 4615] 재미있는 오셀로 게임 (Java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQmA4uK8ygDFAXj 

SW Expert Academy

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SW4615 {
	static int T;
	static int N, M;
	static int[][] map;
	static int[] dy= {-1,1,0,0,-1,-1,1,1};
	static int[] dx= {0,0,-1,1,-1,1,1,-1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		T=Integer.parseInt(br.readLine());
		for (int t=1; t<=T; t++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			M=Integer.parseInt(st.nextToken());
			map=new int[N+1][N+1];
			map[N/2][N/2]=2;
			map[N/2][N/2+1]=1;
			map[N/2+1][N/2]=1;
			map[N/2+1][N/2+1]=2;
			int x, y, color;
			for (int i=0; i<M; i++) {
				st=new StringTokenizer(br.readLine());
				x=Integer.parseInt(st.nextToken());
				y=Integer.parseInt(st.nextToken());
				color=Integer.parseInt(st.nextToken());
				map[y][x]=color;
				find(y,x);
			}
			int black=0;
			int white=0;
			for (int i=1; i<=N; i++) {
				for (int j=1; j<=N; j++) {
					if (map[i][j]==1) {
						black++;
					}
					else if (map[i][j]==2) {
						white++;
					}
				}
			}
			System.out.printf("#%d %d %d\n", t, black, white);
		}

	}
	private static void find(int y, int x) {
		for (int d=0; d<8; d++) {
			if (dfs(y, x, d, map[y][x])==1 && map[y+dy[d]][x+dx[d]]!=map[y][x]) {
				break;
			}
		}
	}
	
	private static int dfs(int y, int x, int d, int c) {
		int ny=y+dy[d];
		int nx=x+dx[d];
		if (isValid(ny,nx)){
			if (map[ny][nx]!=c) {
				if (dfs(ny, nx, d, c)==1) {
					map[ny][nx]=c;
					return 1;
				}
				else {
					return 0;
				}
			}
			else {
				return 1;
			}
		}
		return 0;
		
	}
	
	
	private static boolean isValid(int y, int x) {
		return !(y<=0 || x<=0 || y>N || x>N || map[y][x]==0);
	}

}

 

dfs로 풀었다.

8방향 중 한 방향을 골라 범위 안에 있고, 지금 놓으려고 하는 돌과 반대의 색인 돌이 나올 경우 또 dfs 탐색을 해주고..

지금 놓으려는 돌과 같은 색의 돌이 나올 때 return을 1로 해줘서, caller로 돌아갈 때 자동적으로 지금 놓으려고 하는 돌의 색으로 채워준다. 그 이외의 경우는 return을 0으로 한다.

8방향 중 한 방향을 골라 dfs 탐색한 결과가 1이고, 지금 놓으려고 하는 돌+바로 옆의 돌이 다른 색의 돌일 경우 문제의 조건을 만족하므로 더이상 다른 방향을 탐색하지 않는다. 

 

다른 분들(https://herong.tistory.com/entry/SWEA-4615-%EC%9E%AC%EB%AF%B8%EC%9E%88%EB%8A%94-%EC%98%A4%EC%85%80%EB%A1%9C-%EA%B2%8C%EC%9E%84-D3-Simulation)의 코드를 보니,

while 문으로 계속해서 한 방향으로 탐색한 뒤 (놓으려고 하는 돌과 반대 색상의 돌일 경우 계속 while 을 돌리고, 놓으려고 하는 돌과 같은 색상의 돌을 만날 경우 while 문을 빠져나온다, 이 반복문 역시도 범위를 벗어나거나 빈칸을 만날 때 while 문을 빠져나옴),

nr과 nc에 있는 돌의 색이 현재 r,c 돌의 색과 같을 경우, dr[d], dc[d] 를 줄여나가면서 nr과 nc가 r,c 가 될 때까지 같은 색으로 채워나간다.