[Algorithm] SW Expert Academy - 2105. [모의 SW 역량테스트] 디저트 카페 해설

삼성 SW 모의 테스트

 

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

 

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

 

 

사용한 개념

 

1. BFS탐색

2. 시뮬레이션

 

이 문제에서 BFS탐색을 하는데 있어 이전 탐색 방향에 따라, 현재 탐색 방향을 지정해주는 것이 포인트입니다.

 

즉, 문제에서 주어진 4가지 대각선 방향에 있어 이전 방향이 ↘ 방향이면, 현재 탐색할 방향은 ↙ OR ↘ 입니다. 이런식으로 각각의 이전 방향에 대한 현재 탐색 방향을 지정해줘서 사각형을 그릴 수 있도록 만들어 줍니다.

 

 

아래는 전체소스 입니다.

package SWE;

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

public class SWTest_2105 {
	static String map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		int ansList[] = new int[tc];
		for(int t=0; t<tc; t++){
			int n = Integer.parseInt(br.readLine());
			map = new String[n][n];
			for(int i=0; i<map.length; i++){
				String str = br.readLine();
				String strArr[] = str.split(" ");
				for(int j=0; j<map[0].length; j++){
					map[i][j] = strArr[j];
				}
			}
			
			
			for(int i=0; i<map.length; i++){
				for(int j=0; j<map[0].length; j++){
					drawRec(i, j, i, j, 0, map[i][j], 1);
				}
			}
			
			
			ansList[t] = ans;
			ans = -1;
			
		}
		for(int i=0; i<ansList.length; i++)System.out.println("#"+(i+1)+" "+ansList[i]);
	}

	static int dX[] = {1,  1, -1, -1};
	static int dY[] = {1, -1, -1,  1};
	static int ans = -1;
	private static void drawRec(int initX, int initY, int x, int y, int d, String his, int cnt) {

		for(int i=0; i<4; i++){
			if(d==0 && (i==2 || i==3)) continue;
			if(d==1 && (i==0 || i==3)) continue;
			if(d==2 && (i==0 || i==1)) continue;
			if(d==3 && (i==0 || i==1 || i==2)) continue;
			if(his.length() == 1 && i==1) continue; //최초만 1방향으로 못가게 한다. 
			int nX = x + dX[i];
			int nY = y + dY[i];
			
			if(-1<nX && nX<map.length && -1<nY && nY<map[0].length){	
				if(nX == initX && nY == initY){//사각형이 종료되는 시점
					if(ans < cnt){//ans 갱신 후 종료
						ans = cnt;
					}
					return;
				}
				String[] hisArr = his.split(" ");
				boolean goStop = true;
				for(int j=0; j<hisArr.length; j++){//과거 방문하지 않은경우만 방문	
					if(hisArr[j].equals(map[nX][nY])){
						goStop = false;
						break;
					}
				}
				if(goStop)drawRec(initX, initY, nX, nY, i, his+" "+map[nX][nY], cnt+1);
		
			}
		}
		
	}


}