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

• 시간 : 50개 테스트케이스를 합쳐서 C의 경우 3초 / C++의 경우 3초 / Java의 경우 3초 / Python의 경우 15초

• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

세상 어려웠다. DFS를 이용하여 푼 문제.

 

시계방향이나 반시계방향이나 같기 때문에 나는 반시계방향으로만 돌기로 결정했다.

dx,dy에는 인덱스 맞추기 위해서 0을 추가했다.

디저트가게마다 디저트의 수가 겹치지 않는지 확인하기 위해서는 문자열 contains 함수를 사용했는데,

공백이나 표시처리 없이 넣어버리면 숫자가 구분이 모호해져서 앞뒤로 공백을 넣었다.

1 23 11 이라는 숫자가 있을때

공백x => 12311 - 뭔지모름

한쪽만 구분주기 , 콤마기호 로 => 1,23,11, - 1,을 검색했을때 2개가 나옴.. 11,도 1,로 인식

양쪽다 구분주기 " " 공백 기호 => 1  23  11  - 공백붙여서 검색하면 잘 구분되어짐

import java.util.Scanner;
import java.io.FileInputStream;


class Solution
{
    static int N;
	static int[] dx = {0,1,1,-1,-1};
	static int[] dy = {0,-1,1,1,-1};
	static int[][] map;
	static boolean[][] visit;
	static int result = Integer.MIN_VALUE;
	static String strCnt;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int tc= 0;tc<T;tc++) {
			N = sc.nextInt(); // 배열 범위
			
			map = new int[N][N];
			visit = new boolean[N][N];
			result=-1;
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					map[i][j]= sc.nextInt();
				}
			}
			//================================
			
			for(int i=0;i<map.length;i++) {
				for(int j=0;j<map.length;j++) {
					
					eat(i, j, i, j, 1, 1," "+map[i][j]+" ");
				}
			}
			if(result<4)
				result = -1;
			
			System.out.println("#"+(tc+1)+" "+result);
		}
	}
	
	public static void eat(int firstRow,int firstCol,int row,int col, int dir, int cnt, String menu) {
		//0. 변수 설명
//		int firstRow 	: 처음 시작점 행
//		int firstCol 	: 처음 시작점 열
//		int row			: 현재 행
//		int col			: 현재 열
//		int dir			: 방향 몇번 꺾었는지? - 4번꺾어야 사각형이 되니까 4번기준
//		int cnt			: 디저트 가게 들린 수
//		String menu		: 순서대로 들렸던 디저트 가게들의 디저트 수

		
		//1. 종료조건	
		if(dir==4) {
			if(row+dx[dir] == firstRow && col+dy[dir] == firstCol) {
				result = Math.max(result, cnt);
				return;
			}
		}
        if(dir==5) return;

		//2. 방향탐색
		int nx = row + dx[dir];
		int ny = col + dy[dir];

		
		//2-1. 배열의 범위 벗어났는지 체크
		if(nx >= N || ny >= N || nx < 0 || ny < 0) {
			//System.out.println("소멸");
			return;
		}
		
		//2-2. 이미 들렸던 곳인지 체크
		if(visit[nx][ny]){
			//System.out.println("소멸");
			return;
		}
		//2-3. 디저트의 개수가 같은 곳인지 체크
		if(menu.contains(" "+String.valueOf(map[nx][ny])+" ")){
			//System.out.println("소멸");
			return;
		}
	
		visit[nx][ny]=true;
		//같은 방향으로 돌기
		eat(firstRow,firstCol,nx,ny,dir,cnt+1,menu+" "+map[nx][ny]+" ");
		//방향 꺾어서 돌기
		eat(firstRow,firstCol,nx,ny,dir+1,cnt+1,menu+" "+map[nx][ny]+" ");
		visit[nx][ny]=false; //false처리 이유: 함수를 돌다가 조건에 맞지 않아서 return으로 돌아왔을때, 이전 상황과 같이 만들어 주기 위함.
		
	}
}

 

삽질 했던 부분은 종료조건 일 때였다.

if(dir==4)이면 firstRow,Col 체크함과 상관없이 무조건 return;하는 것으로 생각했는데,

방향을 바꾸지않고 같은방향으로 계속 들어가는 경우가 있었다.

		//1. 종료조건	
		if(dir==4) {
			if(row+dx[dir] == firstRow && col+dy[dir] == firstCol) {
				result = Math.max(result, cnt);
				return;
			}
            //return; 여기에 리턴넣어버리면 dir 4 방향으로 계속 한평생 1칸밖에 못가고 다나가져버린..
		}
		if(dir==5) return;

 

 

 

들렸던 곳인지  check하는 방법은 배열로도 가능하다.

package algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class SWEA2105 {

	static int N;
	static int[] dx = {0,1,1,-1,-1};
	static int[] dy = {0,-1,1,1,-1};
	static int[][] map;
	static boolean[][] visit;
	static boolean[] nVisited;
	static int result = Integer.MIN_VALUE;
	static String strCnt;
	
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("2105input.txt"));
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int tc= 0;tc<T;tc++) {
			N = sc.nextInt(); // 배열 범위
			
			map = new int[N][N];
			visit = new boolean[N][N];
			nVisited = new boolean[101];
			result=-1;
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					map[i][j]= sc.nextInt();
				}
			}
			//================================
			//eat(map,0,0,0,1,cnt,1,"");
			
			for(int i=0;i<map.length;i++) {
				for(int j=0;j<map.length;j++) {
					visit[i][j]=true;
					//nVisited[map[i][j]] = true;
					eat(i, j, i, j, 1, 1," "+map[i][j]+" ");
					visit[i][j]=false;
					//nVisited[map[i][j]] = false;
				}
			}
			if(result<4)
				result = -1;
			
			System.out.println("#"+(tc+1)+" "+result);
			//System.out.println("===========================");
		}
	}
	
	public static void eat(int firstRow,int firstCol,int row,int col, int dir, int cnt, String menu) {
		//0. 변수 설명
//		int firstRow 	: 처음 시작점 행
//		int firstCol 	: 처음 시작점 열
//		int row			: 현재 행
//		int col			: 현재 열
//		int dir			: 방향 몇번 꺾었는지? - 4번꺾어야 사각형이 되니까 4번기준
//		int cnt			: 디저트 가게 들린 수
//		String menu		: 순서대로 들렸던 디저트 가게들의 디저트 수
		
		
		//System.out.println(menu);
		//System.out.println("{"+row+","+col+"} ,"+dir);
		
		//1. 종료조건	
		if(dir==4) {
			if(row+dx[dir] == firstRow && col+dy[dir] == firstCol) {
				result = Math.max(result, cnt);
				return;
			}
			
		}
		if(dir==5) return;
//		
//		if(row+dx[dir] == firstRow && col+dy[dir] == firstCol && cnt!=1) {
//			result = Math.max(result, cnt);
//			return;
//		}

		//2. 방향탐색
		int nx = row + dx[dir];
		int ny = col + dy[dir];

		
		//2-1. 배열의 범위 벗어났는지 체크
		if(nx >= N || ny >= N || nx < 0 || ny < 0) {
			//System.out.println("소멸");
			return;
		}
		
		//2-2. 이미 들렸던 곳인지 체크
		if(visit[nx][ny]){
			//System.out.println("소멸");
			return;
		}
		//2-3. 디저트의 개수가 같은 곳인지 체크
		if(menu.contains(String.valueOf(" "+map[nx][ny])+" ")){
		//if(nVisited[map[nx][ny]]){
			//System.out.println("소멸");
			return;
		}
	

		
		//System.out.println("+"+menu);
		visit[nx][ny]=true;
		//nVisited[map[nx][ny]] = true;
		//같은 방향으로 돌기
		eat(firstRow,firstCol,nx,ny,dir,cnt+1,menu+" "+map[nx][ny]+" ");
		//방향 꺾어서 돌기
		eat(firstRow,firstCol,nx,ny,dir+1,cnt+1,menu+" "+map[nx][ny]+" ");
		
		visit[nx][ny]=false; //false처리 이유: 함수를 돌다가 조건에 맞지 않아서 return으로 돌아왔을때, 이전 상황과 같이 만들어 주기 위함. visit배열은 공유하고 있기 때문에
		//nVisited[map[nx][ny]]=false;
	}

}