[코테] 백준 : 14500 테트로미노

이번문제는 문제를 이해하고, 어느정도 해결책까지는 접근할 수 있었으나, 아직 dfs(깊이우선탐색)에 대한 문제를 많이 풀어보지 않았기때문에, dfs관련 문제인지 파악하지 못했던거 같다. dfs는 자주 출제되는 문제유형이니 잘 공부하도록하자.

 

우선 처음 접근할때는 규칙을 찾으려고 노력했다. 하지만 모두 공통된 규칙을 찾기에는 쉽지 않았다. 

찾아보니 dfs문제임을 알 수 있었다. 그 이유는 처음 한 조각을 고르면 4변에 붙일 수 있고, 붙이고 나면 그 다음블록에는 3변에 붙일 수 있고, 그 다음은 3블록 (4X3X3)이런식으로 붙일 수 있다는 규칙이 있었다.

 

하지만, 이게 왜 dfs인지 알아야한다. 처음 한칸을 시작으로 4가지 경우, 그리고 3가지 경우, 그리고 3가지 경우로 발생되며, 이때 나온 합들 중 가장 큰 값을 고르는 문제이기에 깊이우선탐색을 적용하면 된다.

 

깊이우선탐색은 생각하기에 쉬운 문제이지 않으나, 많이 출제되기에 많은 문제를 풀어 익숙해져보자.

 

여기서 알아두면 좋은 팁 몇가지를 나열하고 넘어가도록 하자.

1.  * Private 멤버는 class 외부에서 접근할 수 없는 변수를 
     * Public 멤버는 class 외부에서 접근할 수 있는 변수를 의미합니다.

 

2. static으로 설정하면 같은 곳의 메모리 주소만을 바라보기 때문에 static 변수의 값을 공유하게 사용할 수 있다.

 

3. 문자열 입력을 위한 방법

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

   StringTokenizer st;

 

   st = new StringTokenizer(br.readLine());

   int n = Integer.parseInt(st.nextToken());

 

이제 이 문제의 핵심적은 부분을 확인해 본뒤에 아래 코드를 확인하여 실행해 보며 공부해보자.

우선 dfs문제이므로 dfs가 어떤식으로 동작하는 지 알아야한다.

1. dfs는 재귀적으로 돌며 깊이우선탐색을 한다. 이때 종료조건이 있어야 하며,  최하위 깊이에 도달한 후 빠져나올 수 있어여한다.

2. 방문표시를 적절히 사용해 주어야 불필요한 방문을 하지 않고, 빠져나올 수 있다.

 

이제 아래의 코드를 보며 정확히 확인해 보도록하자

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

public class Main {

	/*
	 * Private 멤버는 class 외부에서 접근할 수 없는 변수를 Public 멤버는 class 외부에서 접근할 수 있는 변수를 의미합니다.
	 */
	private static int n, m, input[][], resultSum = 0; // static 으로 설정하면 같은 곳의 메모리 주소만을 바라보기 때문에 static 변수의 값을 공유하게
	private static int dx[] = { 0, 0, 1, -1 };
	private static int dy[] = { 1, -1, 0, 0 };
	private static boolean check[][];

	private static int ex[][] = { { 0, 0, 0, 1 }, { 0, 1, 2, 1 }, { 0, 0, 0, -1 }, { 0, 0, 1, -1 } }; // 이차원배열
	private static int ey[][] = { { 0, 1, 2, 1 }, { 0, 0, 0, 1 }, { 0, 1, 2, 1 }, { 0, 1, 1, 1 } };

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

		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		// 입력배열과 체크값배열을 생성
		input = new int[n+1][m+1];
		check = new boolean[n+1][m+1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= m; j++) {
				input[i][j] = Integer.parseInt(st.nextToken()); // 1~max
				check[i][j] = false;
			}
		}

		// 계산
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				//방문 표시
				check[i][j] = true; 
				
				// 체크를 해제하면 무한루프에 들어가 않을까 걱정할 수 있습니다.
				// 길이로 재귀를 중단시키기 때문에, 수행횟수는 4 * 3 * 3, 한점에서 최대 36번 수행됩니다.
				dfs(i, j, input[i][j], 1);
				
				//미방문 표시 -> 다음 dfs시 해당점을 방문가능하도록 해야하기때문입니다.
				check[i][j] = false; 
				
				// ㅗ,ㅏ,ㅗ,ㅓ 4개의 예외조건
				exception(i, j);
			}
		}
		System.out.println(resultSum);
	}

	private static void dfs(int x, int y, int sum, int len) {

		// 종료조건
		if (len >= 4) {
			resultSum = max(sum, resultSum); // 기존의 합보다 크면 교체
			return;
		}
		
		//사각형의 면은 4개이므로 경우가 최대 4번
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			// 범위를 넘어가는 경우 패스
			if (nx < 1 || nx > n || ny < 1 || ny > m) {
				continue;
			}

			//아직 방문하지 않았다면 
			if (check[nx][ny] == false) {
				//방문 표시
				check[nx][ny] = true; 
				//하나의 탐색을 완료하면 여기로 돌아옵니다.
				dfs(nx, ny, sum + input[nx][ny], len+1); 
				//미방문 표시 -> 다음 dfs시 해당점을 방문가능하도록 해야하기때문입니다.
				check[nx][ny] = false; 
			}
		}

	}
	
	private static int max(int x, int y) {
		return x > y ? x : y;
	}
	
	private static void exception(int x, int y) {
		// ㅗ,ㅏ,ㅗ,ㅓ 4개의 예외조건
		for (int i = 0; i < 4; i++) {
			int exSum =0;
			for (int j = 0; j < 4; j++) {
				int nx = x + ex[i][j];
				int ny = y + ey[i][j];

				// 범위를 넘어가는 경우 패스
				if (nx < 1 || nx > n || ny < 1 || ny > m) {
					break;
				} 
				else { //예외 합계산
					exSum += input[nx][ny];
				}
			}
           resultSum = max(resultSum, exSum);
		}
	}
}

 

참고: https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8