알고리즘 문제풀이/SWEA
[SWEA] 모의 SW 역량 테스트 :: 2105번 디저트 카페 자바 풀이(백트래킹)
- -
sw expert academy 2105번 디저트 카페 자바(java) 풀이
- 모의 SW 역량 테스트
- sw expert academy 2105번 디저트 카페
문제 정리
- 한 변의 길이가 N인 정사각형 모양을 가진 지역이 있다.
- 숫자는 디저트 카페에서 팔고 있는 디저트의 종류 수를 의미한다.
- 카페들 사이를 대각선 방향으로 움직일 수 있으며 사각형 모양으로 움직이고 출발지로 되돌아와야 한다.
- 이동 중에 같은 숫자의 디저트 종류를 가지는 카페에 가면 안된다.
- 하나의 카페에만 방문해서는 안된다.
- 왔던 길을 다시 돌아가도 안된다.
- 가장 많은 카페를 경우하는 케이스를 찾고, 그때 경유 가능한 카페 수를 출력한다.
- 먹을 수 없는 경우는 -1을 출력한다.
- 디저트 번호는 1~100까지 이다.
문제풀이
이동 가능한 경우는 다음과 같이 정합니다.
- 이전에 오른쪽 아래로 이동한 경우: 오른쪽 아래와 왼쪽 아래로 이동 가능
- 이전에 왼쪽 아래로 이동한 경우: 왼쪽 아래와 왼쪽 위로 이동 가능
- 이전에 왼쪽 위로 이동한 경우: 왼쪽 위와 오른쪽 위로 이동 가능
- 이전에 오른쪽 위로 이동한 경우: 오른쪽 위와 오른쪽 아래로 이동 가능
이렇게 위와 같이 이동함으로써 이동가능한 디저트 카페 코스를 따져줍니다.
dfs
모든 경우를 따져주기 위해서 dfs를 순회하였습니다.
순회하면서 다음과 같은 정보들을 저장하여 넘겨줍니다.
- 현 x좌표
- 현 y좌표
1,2번은 현재 위치한 x,y 좌표를 나타냅니다. - 이동한 횟수
경유한 디저트 카페의 수를 기억합니다. - 이전에 이동한 방향
그리고 다음에 이동할 방향을 정하기 위해서 이전에 이동했던 방향을 넘겨줍니다. 이동 방향은 다음과 같이 하였습니다.
<방향>
<xdir[i][j]>0: 오른쪽 아래 1: 왼쪽 아래 2: 왼쪽 위 3: 오른쪽 위
예를 들어 전에 오른쪽 아래로 이동했다면 다음에는 오른쪽 아래나 왼쪽 아래로 이동할 수 있습니다. 다음과 같이 나타내집니다.i: 이전에 이동한 방향 j: 다음에 이동할 방향
오른쪽 아래는 xdir[0][0] = 1, ydir[0][0] = 1 (x 증가, y증가)
왼쪽 아래는 xdir[0][1] = 1, ydir[0][1] = -1 (x 증가, y감소)
나머지 방향들에 대해서도 위와 같은 방식으로 나타내었습니다. - 방향을 튼 횟수
사각형이 만들어지도록 움직인것이 맞는지 확인하기 위해서 방향을 꺾은 횟수도 저장해야 합니다. 총 3번 방향을 꺾은뒤 시작 위치로 돌아오면 사각형이 완성된 것입니다.
x,y과 시작점의 x,y좌표와 같고 3번 꺾어서 시작점에 도착한 경우 사각형을 만든 것으로 여깁니다.
이때 k != 0 을 넣은 이유는 이제 이동을 시작한 경우를 걸러내기 위해서 입니다. (이동을 시작하자마자 dfs를 들어오면 바로 시작위치와 같기 때문에 이를 방지)
이전에 경유한 카페의 디저트 수
처음에는 이동한 곳의 디저트 수를 모두 list에 담아서 조사하였습니다. 하지만 이는 시간이 오래 걸리게 됩니다.
list를 이용하지 않고, 방문한 카페의 디저트 수와 같은지 조사하기 위해서 boolean 1차원 배열을 만들어 관리합니다.
디저트 수가 2인 곳을 방문했다면 nVisited[2] = true가 됩니다. 이를 이용하여 같은 디저트 수를 갖는 곳은 피할 수 있습니다.
가지치기
다음 부분이 가지치기를 해낸 부분입니다.
- 시작 위치에서 오른쪽 아래로만 탐색
위 코드를 집어 넣지 않았더니 시간초과가 발생했지만 추가함으로써 통과할 수 있었습니다.if(k==0 && i == 1) continue;
위 코드의 의미는 출발점에서 오른쪽 아래로 이동해서 사각형을 만드는 경우만 따짐으로써 중복 검색을 방지하는 것입니다.
오른쪽 아래로만 돌아서 사각형을 만드는 경우만 따져 주면 모든 경우를 검사할 수 있기 때문입니다.
위에 수는 코드를 적용하지 않았을 경우 dfs 함수가 불려진 횟수 이고 밑에는 코드를 적용했을 경우 불려진 횟수입니다.
2배가 넘게 차이가 나는 것을 볼 수 있습니다.
- 2452521
- 962482
- 사각형을 만들 수 없는 경우
크게 신경쓰지 않아도 되는 부분입니다.
맨 밑의 두 행, 맨 왼쪽 열, 맨 오른쪽 열에서는 사각형을 만들 수 없다. 이 경우는 탐색하지 않습니다.
디저트 카페 자바 dfs 풀이 코드
아래에 bfs로 푼 코드도 있습니다!!
이해하기는 아래 코드가 더 쉬울거에요
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Solution {
static int max;
static int N;
static int[][] map;
// 0: 오른쪽 아래, 1: 왼쪽 아래, 2: 왼쪽 위, 3: 오른쪽 위
// 0, 1, 2, 3
// {0,1}, {1,2}, {2,3}, {3,0}
static int[][] xdir = {{1,1}, {1,-1}, {-1,-1}, {-1,1}};
static int[][] ydir = {{1,-1},{-1,-1},{-1,1},{1,1}};
static boolean[][] visited;
static boolean[] nVisited;
static int startX, startY;
static int startNum;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
// 입력받기
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i=0; i<N; i++){
String[] temp = br.readLine().split(" ");
for(int j=0; j<N; j++){
map[i][j] = Integer.parseInt(temp[j]);
}
}
max = -1;
visited = new boolean[N][N];
nVisited = new boolean[101];
// 모든 위치에서 dfs 탐색
// 맨 아래 두행, 맨 왼쪽 열, 맨 오른쪽 열은 사각형 만들기 불가로 제외
for(int i=0; i<N-2; i++){
for(int j=1; j<N-1; j++){
// 시작 위치와 시작점의 디저트 수 저장
startX = i;
startY = j;
startNum = map[i][j];
dfs(i,j, 0, 0, 0);
}
}
System.out.println("#" + test + " " + max);
}
br.close();
}
public static void dfs(int x, int y, int k, int dir, int rotate){
// 시작 위치에 도착 & 사각형 완성
if(k != 0 && startX == x && startY == y && rotate == 3){
max = max < k ? k : max; // 최대값 갱신
return;
}
for(int i=0; i<2; i++){
// 시작점에서 오른쪽 아래로 내려가는 경우만 따짐으로써
// 중복 제거
if(k==0 && i == 1)
continue;
int dx = x + xdir[dir][i];
int dy = y + ydir[dir][i];
// 유효한 위치이면서 방문하지 않은 곳
if(isValidPosition(dx, dy) && !visited[dx][dy]){
// 이전에 방문했던 곳(시작 점 포함)의 값들과 달라야 함
// 시작점으로 돌아온 경우는 같을 수 밖에 없기 때문에 그 부분은 오른쪽 조건으로 예외처리
if((!nVisited[map[dx][dy]] && startNum != map[dx][dy])|| ((dx == startX) && (dy == startY))){
visited[dx][dy] = true;
nVisited[map[dx][dy]]= true;
if(rotate != (dir+i)%4)
dfs(dx, dy, k+1, (dir+i)%4, rotate+1); // 같은 방향으로 가지 않기 때문에 방향을 꺾은 것으로 판단
else
dfs(dx, dy, k+1, (dir+i)%4, rotate); // 같은 방향으로 가는 경우는 꺾지 않은 것이므로 rotate 그대로 전달
nVisited[map[dx][dy]]= false;
visited[dx][dy] = false;
}
}
}
}
public static boolean isValidPosition(int x, int y){
if(x < 0 || x >= N || y < 0 || y >= N) return false;
return true;
}
}
디저트 카페 bfs 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class Pos{
int x;
int y;
int dir;
HashSet<Integer> set;
Pos(int x, int y, int dir){
this.x = x;
this.y = y;
this.dir = dir;
this.set = new HashSet<>();
}
Pos(int x, int y, int dir, HashSet<Integer> set){
this.x = x;
this.y = y;
this.dir = dir;
this.set = set;
}
}
class Solution2_bfs {
/*
* 대각선 방향으로만 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다
* 또한, 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다
* 하나의 카페에서 디저트를 먹는 것도 안된다
* 왔던 길을 다시 돌아가도 안된다
* 디저트를 최대한 많이 먹으려고 한다
* 디저트를 먹을 수 없는 경우 -1
* 디저트의 종류를 나타내는 수는 1이상 100이하
* */
static int max;
static int N;
static int[][] map;
// 좌상, 우상, 좌하, 우하
static int[] xdir = {-1,-1,1,1};
static int[] ydir = {-1,1,-1,1};
static ArrayList<int[]> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i=0; i<N; i++) {
String[] temp = br.readLine().split(" ");
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(temp[j]);
}
}
init();
max = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
bfs(i,j);
}
}
if(max != 0)
System.out.println("#" + tc + " " + max);
else
System.out.println("#" + tc + " " + -1);
}
}
public static void bfs(int a, int b) {
Queue<Pos> q = new LinkedList<>();
//처음엔 무조건 우하로만 이동
int dx = a + xdir[3];
int dy = b + ydir[3];
if(isValidPosition(dx, dy) && map[a][b] != map[dx][dy]) {
q.offer(new Pos(dx, dy,3));
q.peek().set.add(map[dx][dy]);
q.peek().set.add(map[a][b]);
}
else
return;
while(!q.isEmpty()) {
Pos p = q.poll();
int x = p.x;
int y = p.y;
int dir = p.dir;
int[] ddir = list.get(dir);
for(int i=0, len=ddir.length; i<len; i++) {
dx = x + xdir[ddir[i]];
dy = y + ydir[ddir[i]];
// 처음 위치로 돌아온 경우
if(dx == a && dy == b) {
int size = p.set.size();
max = max < size ? size : max;
continue;
}
if(isValidPosition(dx, dy)) {
// 같은 숫자의 디저트가 아님
if(!p.set.contains(map[dx][dy])) {
HashSet<Integer> copy = new HashSet<>();
copy.addAll(p.set);
copy.add(map[dx][dy]);
q.offer(new Pos(dx, dy, ddir[i], copy));
}
}
}
}
}
public static void init() {
list = new ArrayList<>();
// 좌상, 우상, 좌하, 우하 (0,1,2,3)
list.add(new int[] {0,1}); // 좌상이동의 경우 다음 가능한 이동 경로: 좌상, 우상
list.add(new int[] {1}); // 우상 이동의 경우 다음 가능한 이동 경로: 우상
list.add(new int[] {2,0}); // 좌하 이동의 경우 다음 가능한 이동 경로: 좌하,좌상
list.add(new int[] {2,3}); // 우하 이동의 경우 다음 가능한 이동 경로: 우하,좌하
}
public static boolean isValidPosition(int x, int y) {
if(x < 0 || y < 0 || x >= N || y >= N) return false;
return true;
}
}'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글
| [SWEA] 7699번 수지의 수지 맞는 여행 자바(java) 풀이 (dfs) (0) | 2020.03.07 |
|---|---|
| [SWEA] 1242번 암호코드 스캔 자바(java) 풀이 (0) | 2020.03.06 |
| [SWEA] 모의 SW 역량 테스트 :: 2383번 점심 식사시간 (조합, 시뮬레이션) (0) | 2020.03.05 |
| [SWEA] 모의 SW 역량 테스트 :: 1949번 등산로 조성 (dfs, 백트래킹) (0) | 2020.03.04 |
| [SWEA] 1242번 최적 경로 자바 풀이(dfs, 순열 / DP 풀이) (0) | 2020.03.03 |
Contents
소중한 공감 감사합니다