[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페

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

SW Expert Academy

디저트 카페 문제는 아래 그림처럼 사각형 모양으로 움직여서 원점으로 돌아와야 한다.

원안의 숫자(디저트의 종류)가 겹치면 안 되며 범위를 벗어나도 안된다

더 자세한 조건은 문제 사이트 참고!
 

 

풀이

먼저 N의 범위가 크지 않으므로 모든 경우를 해볼 수 있다. 따라서 DFS를 이용해서 풀었다.

1. 각 칸을 시작점으로 하는 사각형을 모두 만들어준다. 
2. 사각형을 만들 수 없는 N-1 행과 N-2행, 0열과 N-1열은 시작점에서 제외한다.

 

move 함수로 DFS를 해주는데 조건을 잘 처리해주어야 한다.

1. 방향은 오른쪽 아래 방향(1,1), 왼쪽 아래 방향(1,-1), 왼쪽 위 방향(-1,-1), 오른쪽 위 방향(-1,1)의 순서를 정해놓고 움직인다.
2. 이동시킨 곳이 범위를 벗어나지 않아야 하고 방향은 3(시작점으로 돌아가는 마지막 방향)을 넘지 않는다.
3. 움직일 때마다 해당 디저트 종류를 ArrayList에 추가하였다. 계속 탐색을 진행하면서 디저트 종류가 ArrayList에 이미 포함되지 않은 경우에만 탐색을 계속 진행한다.(같은 디저트를 먹지 않는 조건)
4. 탐색을 할 때는 현재 방향을 유지해서 이동하는 경우와 방향을 꺾는 경우(dir 인덱스 증가)를 해주었다.
5. 탐색 시작점에서는 현재 방향을 유지하는 경우만 해줘야 한다(직사각형 모양을 위해 바로 꺾지 못함)
6. 현재 방향이 마지막 방향(오른쪽 위)이고 시작점에 돌아왔으면 max값과 디저트 종류를 추가한 ArrayList의 사이즈를 비교한 뒤 return 한다.

 

코드 주석에 설명 추가

import java.io.*;
import java.util.*;

public class Solution {
	
	static int N, max, sx, sy;
	static int[][] map;
	static int[] dx = {1,1,-1,-1};
	static int[] dy = {1,-1,-1,1};
	static ArrayList list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int tc=1;tc<=T;tc++) {
			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());
				}
			}
            
            
			list = new ArrayList(); //디저트 종류를 추가할 list
			max = -1; //디저트를 먹을 수 없는 경우 -1을 출력하기 위해 -1로 할당
            
            
            //사각형을 만들 수 없는 곳을 제외한 모든 칸에서 탐색 시작
			for(int i=0; i<N-2; i++) {
				for(int j=1; j<N-1; j++) {
					sx = i;
					sy = j;
					list.add(map[sx][sy]);
					move(sx,sy,0);
					list.clear(); //다음 칸에서 출발하는 경우를 위해 list를 비워준다.
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
    
    //DFS
	static void move(int i, int j, int dir) {
		int x;
		int y;

		
        //현재 방향을 유지하며 이동하는 경우
		x = i+dx[dir];
		y = j+dy[dir];
		if(x >= 0 && y >= 0 && x < N && y < N) {
        
			if(dir == 3 && x == sx && y == sy) {
            	//사각형을 만들고 시작점으로 돌아온 경우
				if(max < list.size()) {
					max = list.size();
				}
				return;
			}
            
            //이동할 칸의 디저트가 list에 포함되어 있지 않아야한다.
			if(!list.contains(map[x][y])) {
				list.add(map[x][y]);
				move(x,y,dir);
				list.remove(list.size()-1);
			}
		}
		
		
        //방향을 꺾는 경우에는 dir+1을 해준 값으로 계산
		if(dir+1 == 4) return; //방향은 최대 3이므로
		if(dir == 0 &&i == sx && j == sy) return; //시작점에서는 꺾을 수 없다.
		x = i+dx[dir+1];
		y = j+dy[dir+1];
		
		if(x >= 0 && y >= 0 && x < N && y < N) {
        
			if(dir+1 == 3 && x == sx && y == sy) {
            	//사각형을 만들고 시작점으로 돌아온 경우
				if(max < list.size()) {
					max = list.size();
				}
				return;
			}
            
            //이동할 칸의 디저트가 list에 포함되어 있지 않아야한다.
			if(!list.contains(map[x][y])) {
				list.add(map[x][y]);
				move(x,y,dir+1);
				list.remove(list.size()-1);
			}
		}		
	}

}

 

 

더 빠른 시간안에 문제를 해결한 사람들의 코드를 보면 dfs를 사용하지 않고 반복문만을 사용하였다. 속도가 거의 두배 넘게 차이가 나는 것 같다. 물론 백트랙킹을 더 잘해주면 차이가 더 적게 날 수도 있을 것 같다... 다음에 dfs를 사용하지 않고 다시 풀어봐야겠다.