[ 백준 / 14500 ] 테트로미노 ( 자바 )

www.acmicpc.net/problem/14500

14500번: 테트로미노

 

 

구현과 DFS라는 생각을 했지만 정작 어떻게 구현해야하는지 굉장히 머리가 아팠다.

생각해 볼만한 있는 중요한 점이 몇 개 있었다.

(0,0)에서 시작하여서 그냥 끝내야 할까?

각 점에서 시작하여서 계산해야 할까?

 

일반적인 DFS를 사용해야 할까?

=> 그렇다면 ㅗ 모양을 출력하지 못한다. 따라서 일반적인 DFS가 아닌 추가적인 방법이 필요하다. 그래서 BFS를 생각했고 Queue를 사용해봤는데,  백트래킹과 BFS를 짬뽕해서 사용해버렸다. 아래에 코드를 올렸다. 백트래킹을 통해 내가 진입했던 칸을 다시 빼주는 작업 해야하는데 이것을 Queue와 함께 사용했더니 제대로 작동되지 않았다. 

 

BFS에서 visited를 사용하기도 하는데, 이는 한번 갔던 곳을 다시 가지 않도록 중복을 막기 위한 것이었다. 따라서 Queue에 추가하는 과정에서 백트래킹은 맞지 않다.  

 

처음으로 돌아가서, 먼저 재귀함수에 들어오면 칸 수를 조사하고 stack에 넣는다. cnt가 4라는 의미는 4개의 칸을 사용했다는 의미이므로 답인지 체크하고 return한다. 4가 아니라면 정상적으로 진행한다. DFS이므로 stack에 넣은 칸은 stack.pop()을 통해서 백트래킹을 할 것이다. 그 사이에 있는 DFS과정은 어떻게 진행될까?

 

현재 내가 가지고 있는 모든 stack에 대해서 순회를 하면서 인접한 칸을 조사한다. 이때도 visited를 통해서 중복을 제거하는데, 지금 내가 가지고 있는 칸에 대해서 visited 중복을 검사한다. 바꿔 말하면, 각 (i,j)에서 모든 칸을 검사하도록 했는데, 검사 간에 중복되는 모형이 나올수도 있다. 단지 최대한 지금 내가 시작한 점 (i,j)에 대해서 visited를 통해서 4개의 칸을 검사하겠다는 의미이다. 

 

이 문제를 통해서 DFS에 대해서 다시 생각해보게 된다. 단순히 2차원 배열에서 원하는 지점까지 깊게 파고들어 가는 것으로 생각을 했다. 또한 visited의 백트래킹만 고려하는게 일반적이었다. 하지만 이 문제에서는 visited 이외에도 stack에 push , pop을 진행하는 것도 백트래킹으로 해야만 했다. 너무 일반적이고 수웠던 문제의 유형에 적응하다보니 이러한 부분을 생각하지 못했다. 즉, DFS로 계속 새로운 점에 접근하고 visited를 통해서 중복된 곳으로 가지 않는 개념은 똑같다. 하지만 새로운 점에서 stack을 통해 현재 위치를 추가하고 cnt=4를 통해 모든 검사가 끝나면 pop을 통해서 정상적으로 백트래킹을 하는 것이 추가적인 부분이었다.

 

*잘못된 코드(BFS와 backtracking을 혼용)

 

import java.util.*;

public class Main {

	static int[][] array;
	static boolean[][] visited;
	static int answer = 0;
	static int[] dx = { 0, 0, 1 };
	static int[] dy = { 1, -1, 0 };
	static int N;
	static int M;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		array = new int[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				array[i][j] = sc.nextInt();
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = true;
				move(array[i][j], 1, i, j);
				visited[i][j] = false;
			}
		}

		System.out.println(answer);
	}

	static class Node {
		int sum, cnt, x, y;

		public Node(int sum, int cnt, int x, int y) {
			this.sum = sum;
			this.cnt = cnt;
			x = this.x;
			y = this.y;
		}
	}

	public static void move(int sum, int cnt, int x, int y) {
		
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(sum,cnt,x,y));
		
		while(!queue.isEmpty() ) {
			Node node = queue.poll();
			
			int _sum = node.sum;
			int _cnt = node.cnt;
			int _x = node.x;
			int _y = node.y;
			
			if (_cnt == 4) {
				if (_sum > answer)
					answer = _sum;
				return;
			}
			
			for (int i = 0; i < 3; i++) {
				int newX = _x + dx[i];
				int newY = _y + dy[i];

				if (newX < 0 || newX == N || newY < 0 || newY == M)
					continue;
				if (visited[newX][newY] == true)
					continue;

				visited[newX][newY] = true;
				queue.add(new Node(_sum+array[newX][newY],_cnt+1,newX,newY));
				visited[newX][newY] = false;
			}
			
		}
		
		

		
	}
}

 

*답안 코드(DFS,stack을 이용)

import java.util.*;

public class Main {
	static int N;
	static int M;
	static int[][] array;
	static boolean[][] visited;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static Stack<DOT> stack = new Stack<>();
	static int maxCnt = 0;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		array = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				array[i][j] = sc.nextInt();
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = true;
				Find(i, j, 1, array[i][j]);
				visited[i][j] = false;
			}
		}
		System.out.println(maxCnt);
	}

	static class DOT {
		int x, y;

		public DOT(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static void Find(int x, int y, int cnt, int sum) {
		if (cnt == 4) {
			if (sum > maxCnt)
				maxCnt = sum;
			return;
		}
		
		stack.push(new DOT(x, y));

		for (int i = 0; i < stack.size(); i++) {
			DOT dot = stack.get(i);
			for (int j = 0; j < 4; j++) {
				int newX = dot.x + dx[j];
				int newY = dot.y + dy[j];

				if (newX < 0 || newY < 0 || newX >= N || newY >= M || visited[newX][newY])
					continue;

				visited[newX][newY] = true;
				Find(newX, newY, cnt + 1, sum + array[newX][newY]);
				visited[newX][newY] = false;
			}
		}

		stack.pop();
	}
}