[DFS/백트래킹] - LV3 - 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어

2023. 12. 8. 18:35· 알고리즘/문제
목차
  1. 🌿 - 문제 설명
  2. 📌- 풀이
  3. 🔥 - 처음 시간 초과 난 코드
  4. 🔥 - 개선한 코드

https://school.programmers.co.kr/learn/courses/30/lessons/150365

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

🌿 - 문제 설명

📌- 풀이

문제를 보고 처음에는 BFS로 {d, l , r , u} 의 순서대로 완전탐색을 하면 되겠구나 생각해서 그렇게 문제를 풀려고 했는데, 전부 다 탐색을 하게 되면 분명 시간 초과가 날 것 같다고 생각해서 다른 방식을 생각해보게 되었다.

 

일단 주어진 문제에서 문자열을 사전순서대로 가장 빠른 순이라고 했기 때문에 dlru순으로 탐색을 하긴 하는데, 이것을 DFS로 탐색을 하게되면 K의 수 만큼 -> 예를들어 k가 5라면

 

ddddd부터 시작해서 ddddl -> ddddr -> 이렇게 탐색하게 되고 가장 먼저 k == 0 이고 목적지에 도착한 문자열이 정답이 되기 때문에 그렇게 구현을 했다. 처음 풀었을 때 시간 초과가 났고, 어떻게 가지치기를 해야할지 고민을 해서 개선을 했다.

 

🔥 - 처음 시간 초과 난 코드


  
class Solution {
static int[] dx = {1,0,0,-1};
static int[] dy = {0,-1,1,0};
static String[] direction = {"d","l","r","u"};
static String result ="";
static int N,M;
static boolean fin = false;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer = "";
N = n;
M = m;
dfs(x-1,y-1,r-1,c-1, k, "");
answer = result.equals("") ? "impossible" : result;
return answer;
}
public void dfs(int startX, int startY,int endX,int endY, int k , String str){
if(k==0 && startX == endX && startY == endY){
result = str;
fin = true;
return;
}
if(k==0 || fin){
return;
}
for(int i =0;i<4;i++){
int nx = startX + dx[i];
int ny = startY + dy[i];
if(0<= nx && nx<N && 0<= ny && ny<M){
dfs(nx,ny,endX,endY, k-1, str+direction[i]);
}
}
}
}

 

 

위의 방식대로 하면 정답이 나오지 않더라도 탐색을 하는 경우가 많기 때문에

아래처럼 현재 위치한 곳과 도착지점의 거리를 구해서 해당 수가 k와 짝수인지 홀수인지 비교해서 짝/홀수가 같다면 탐색할 수 있고, 짝 홀수가 다르다면 갈 수 없는 곳이라 탐색할 필요가 없기 때문에 해당 조건으로 가지치기를 해서 시간초과를 해결했다.

 

🔥 - 개선한 코드


  
class Solution {
static int[] dx = {1,0,0,-1};
static int[] dy = {0,-1,1,0};
static String[] direction = {"d","l","r","u"};
static String result ="";
static int N,M;
static boolean fin = false;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer = "";
N = n;
M = m;
int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
dfs(x-1,y-1,r-1,c-1, k, "",diff);
answer = result.equals("") ? "impossible" : result;
return answer;
}
public void dfs(int startX, int startY,int endX,int endY, int k , String str, int diff){
if(k==0 && startX == endX && startY == endY){
result = str;
fin = true;
return;
}
if(k==0 || fin){
return;
}
for(int i =0;i<4;i++){
int nx = startX + dx[i];
int ny = startY + dy[i];
if(0<= nx && nx<N && 0<= ny && ny<M && diff <=k){
if((diff % 2 == 0 && k % 2 == 0) || (diff %2 == 1 && k %2 == 1)){
dfs(nx,ny,endX,endY, k-1, str+direction[i],Math.abs(nx-endX) + Math.abs(ny-endY));
}
}
}
}
}

 

  1. 🌿 - 문제 설명
  2. 📌- 풀이
  3. 🔥 - 처음 시간 초과 난 코드
  4. 🔥 - 개선한 코드
'알고리즘/문제' 카테고리의 다른 글
  • [BFS] - G4_14466_소가 길을 건너간 이유 6
  • [BFS] - G3_2638_치즈
  • [BFS,DP] - Lv3 - 부대복귀
  • [구현] - Lv2 - 택배 배달과 수거하기
Casteira
Casteira
할 뿐
Casteira
SpongeCake
Casteira
전체
오늘
어제
  • __Main__ (104)
    • 알고리즘 (65)
      • 개념 (6)
      • 문제 (58)
    • 컴퓨터 구조 (9)
      • 자료 구조 (2)
      • OS (7)
    • 웹 (1)
      • 자바 (1)
      • 스프링 (5)
      • SQL (0)
    • 기록 (4)
      • 포트폴리오 (2)
    • 정글 (18)
      • TIL (17)

블로그 메뉴

  • 🗒️ 깃허브
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • framework
  • 백준
  • java
  • annotation
  • 크래프톤
  • 백준 골드
  • 정글
  • 코딩테스트
  • dp
  • springboot
  • spring
  • 크래프톤 정글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
Casteira
[DFS/백트래킹] - LV3 - 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어
테마상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.