[백준] 14500번 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

---

[풀이에 앞서...😮‍💨]

나는 이런 탐색문제 유형에 젬병이다(ㅠㅠ)

그래서 다른 분의 풀이코드를 이해한 뒤 내 방식대로 풀어봤다!

(해당 코드가 없었다면 중요한 포인트를 절대 생각해내지 못했을꺼다

https://hanyeop.tistory.com/416 감사합니다..!)

탐색문제 풀면 재밌는데 풀기가 너무 싫어 하,,,

앞으로 당분간 풀이를 보고 풀더라도 탐색문제를 많이 풀어봐야겠다!!

마지막으로,,, 매일매일 제출을 미룬 날 재촉 하지 않은 에릭에게 감사인사를 하며,,풀이시작

 

[풀이 방법]

4개의 테트로미노

다음과 같은 4개의 테트로미노 중 ㅜ 모양을 제외한 나머지 모양은 일반적인 dfs탐색이 가능하다!

1. 나머지 모양 dfs탐색

     1) 종이의 첫 번째 위치부터 탐색을 시작!

     2) 상하좌우로 이동하며 범위를 벗어나거나 이미 방문한 위치일 경우 다음 방향으로 이동

     3) 폴리오미노(1칸)를 4개를 탐색하면 매개변수로 받은 sum과 answer와 비교한 뒤, 큰 값을 answer에 넣고 탐색 종료

 

2. ㅜ 모양 dfs탐색

     1) ㅜ모양은 폴리오미노를 2개 탐색했을 경우 다음위치로 이동하는 것이 아닌 그 자리에서 다시 탐색을 시작!

        -> 이때 중요한 점은 다음 위치로 이동은 하지 않지만 합은 다음위치의 것을 더해주어 매개변수로 넘겨준다는 것이다

      2) 폴리오미노 4개를 탐색하면 매개변수로 받은 sum과 answer와 비교한 뒤, 큰 값을 answer에 넣고 탐색 종료

 

💫[1. 나머지 모양 dfs탐색] 안에 조건을 주어 [2. ㅜ 모양 dfs탐색] 을 실행 할 수 있도록 구현💫

 

[코드_Java]

import java.util.Scanner;

public class Main {
	static int N, M, answer;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		//입력받은 값 각 변수에 저장 
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N][M];
		map = new int[N][M];
		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) {
				map[x][y] = sc.nextInt();
			}
		}
		
		//map의 모든 좌표를 출발점으로 탐색시작 
		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) {
				visited[x][y] = true;
				dfs(x, y, map[x][y], 1);
				visited[x][y] = false;
			}
		}
		
		System.out.println(answer);
		
	}
	
	public static void dfs(int x, int y, int sum, int cnt) {
		
		//테트로미노 모양 완성시 탐색 종료
		if(cnt == 4) {
			answer = Math.max(answer, sum);
			return;
		}
		
		//상하좌우로 이동 
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//다음위치가 범위를 넘어가거나 이미 방문한 위치라면 다음 방향으로 이동 
			if(nx < 0 || nx >= N || ny < 0|| ny >= M || visited[nx][ny]) continue;
			
			if(cnt == 2) { //ㅗ모양을 체크하기 위해 해당 위치에서 탐색 반복 
				visited[nx][ny] = true;
				dfs(x, y, sum + map[nx][ny], cnt + 1);
				visited[nx][ny] = false;
			}
			
			//나머지 모양 체크하기 위해 다음위치로 이동하여 탐색 반복 
			visited[nx][ny] = true;
			dfs(nx, ny, sum + map[nx][ny], cnt + 1);
			visited[nx][ny] = false;
		}
		
	}
}

*추가적인 궁금증

클래스 변수인 answer은 선언만 되고 초기화는 따로 하지 않았다! 하지만 Math.max(answer, sum)이 가능하다니?!

찾아보니 클래스 영역에서 변수를 선언한다면 프로그램이 자동으로 알아서 기본 값을 저장해준다고 한다.

(왜지...? 이거에 대해 자세히 공부해봐야겠다)