[SWEA] 2105.디저트 카페 / DFS

@DFS / 35m

쉬운 문제였다.

그런데 마지막 사각형이 만들어질 때 예외처리를 해주지 않으면 직사각형이 아닌 다른 모양으로 만들어져서, 테케가 틀리게 나온다.

그 부분만 신경쓰면 끝나는 문제.

 

 

문제 링크

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

SW Expert Academy

 

 

구현 방법

# 문제의 화살표 방향과 반대로 구현했을 때의 풀이방법이다. (별 의도는 없고 하다보니..)

 

1. 사각형에서 제일 위에 있는 점에서 시작했다.

이중 for문을 돌면서 (이때 세로는 0 <= i < N - 1, 가로는 1 <= j <= N - 1 로 했다.)

시작할 점을 찾는다.

 

 

2. 일반적인 사방탐색과 다르게, 대각선 방향으로 움직이므로

첫 점에서 왼쪽 아래, 두번째 점에서는 오른쪽 아래, 세번째 점에서는 오른쪽 위, 네번째 점에서는 왼쪽 위로 움직인다.

그래서 int[] dx = {1, 1, -1, -1}, dy = {-1, 1, 1, -1}; 이렇게 배열 값을 설정했다.

 

 

구현 포인트

1. 진행 방향은 지금 방향을 유지하느냐, 다음 방향으로 바꾸느냐 두 가지이다.

그래서 for문을 두번 돌리고(i는 0또는 1) , 방향에 대해서는 (지금방향 + i) % 4 이렇게 해주면, 직진 또는 방향을 꺾어서 dfs가 돌게 된다.

 

2. 문제는, 1번 처럼만 처리해주면 테케를 돌렸을때 값이 답보다 크게 나온다.

이유는 그냥 for문을 돌리면 선이 4번에서 끝나는게 아니라 더 그어지는 경우가 생기기 때문이었다.

그래서 만약 지금 4번째 선을 긋고 있는 중이라면, 이때는 방향을 꺾지 않게끔 if문을 하나 넣어줬더니 정상적으로 돌아갔다.

 

 

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

public class Solution {

	private static int N, map[][], maxCount;
	private static int[] dx = {1, 1, -1, -1}, dy = {-1, 1, 1, -1};
	private static boolean[] visit;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			maxCount = -1;
			visit = new boolean[101];
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++)
					map[i][j] = Integer.parseInt(st.nextToken());
			}
			findStart();
			sb.append("#" + t + " " + maxCount + "\n");
		}
		System.out.println(sb);
	}

	private static void findStart() {
		for (int i = 0; i < N - 1; i++) {
			for (int j = 1; j < N - 1; j++) {
				visit[map[i][j]] = true;
				dfs(i, j, 0, i, j, 1);
				visit[map[i][j]] = false;
			}
		}
	}

	private static void dfs(int x, int y, int d, int sx, int sy, int count) {
		for (int i = 0; i < 2; i++) {
			if (d + i == 4) return; 
			int dir = (d + i) % 4;
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;	//visit은 도착점체크한 후에 체크하기
			
			if (sx == nx && sy == ny) {
				if (maxCount < count) maxCount = count;
				return;
			}
			
			if (visit[map[nx][ny]]) continue;
			
			visit[map[nx][ny]] = true;
			dfs(nx, ny, dir, sx, sy, count + 1);
			visit[map[nx][ny]] = false;
		}
	}
}

 

끝!