SWEA_D4_7733_치즈도둑

07월 09일 in Category / Algorithm

SWEA

7733. 치즈도둑

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

public class Solution  {
	static int T, N, X, MIN, MAX, PIECE, pieceCnt;
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int cheese[][];
	static boolean visited[][];

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(in.readLine().trim());
		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(in.readLine().trim());

			MIN = 101;
			MAX = 0;
			PIECE = 1;

			cheese = new int[N + 2][N + 2];
			visited = new boolean[N + 2][N + 2];
			for (int i = 1; i <= N; i++) {
				st = new StringTokenizer(in.readLine());
				for (int j = 1; j <= N; j++) {
					cheese[i][j] = Integer.parseInt(st.nextToken());
					MIN = Math.min(MIN, cheese[i][j]);
					MAX = Math.max(MAX, cheese[i][j]);
				}
			}

			for (X = MIN; X < MAX; X++) {
					pieceCnt = 0;
					visitedInit();
					eat(X);
					findStartPoint();
					PIECE = Math.max(PIECE, pieceCnt);
			}
			System.out.println("#"+test_case+" "+PIECE);
		}
	}
	private static void visitedInit() {
		for(int i=1; i<=N; i++) {
			Arrays.fill(visited[i], false);
		}
	}

	private static void findStartPoint() {
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(!visited[i][j] && cheese[i][j]!=0) {
					pieceCnt++;
					visited[i][j] = true;
					dfs(i, j);
				}
			}
		}
	}

	private static void eat(int day) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (cheese[i][j] == day) {
					cheese[i][j] = 0;
				}
			}
		}
	}

	private static void dfs(int r, int c) {
		int dr, dc;

		for (int d = 0; d < 4; d++) {
			dr = r + dir[d][0];
			dc = c + dir[d][1];
			if(!visited[dr][dc] && cheese[dr][dc]!=0) {
				visited[dr][dc] = true;
				dfs(dr, dc);
			}
		}
	}

}

</br> </br> </br>

visited 안쓰려고 3차원 배열을 써봤다. 메모리도 시간도 더 걸렸다. 실패…

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

public class Solution  {
	static int T, N, X, MIN, MAX, PIECE, pieceCnt;
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int cheese[][][];

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(in.readLine().trim());
		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(in.readLine().trim());

			MIN = 101;
			MAX = 0;
			PIECE = 1;

			cheese = new int[N + 2][N + 2][101];

			for (int i = 1; i <= N; i++) {
				st = new StringTokenizer(in.readLine());
				for (int j = 1; j <= N; j++) {
					X = Integer.parseInt(st.nextToken());
					Arrays.fill(cheese[i][j], 1, X+1, 1);
					MIN = Math.min(MIN, X);
					MAX = Math.max(MAX, X);
				}
			}

			for (X = MIN; X <= MAX; X++) {
				pieceCnt = 0;
				findStartPoint();
				PIECE = Math.max(PIECE, pieceCnt);
			}
			System.out.println("#" + test_case + " " + PIECE);
		}
	}

	private static void findStartPoint() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (cheese[i][j][X] == 1) {
					pieceCnt++;
					cheese[i][j][X] = 0;
					dfs(i, j);
				}
			}
		}
	}

	private static void dfs(int r, int c) {
		int dr, dc;

		for (int d = 0; d < 4; d++) {
			dr = r + dir[d][0];
			dc = c + dir[d][1];
			if (cheese[dr][dc][X] == 1) {
				cheese[dr][dc][X] = 0;
				dfs(dr, dc);
			}
		}
	}

}