리렌더링이 되어서 함수가 파괴가 되어 참조를 못 하는 문제를 해결하기 위해 sendRequest 함수 자체에는 useCallback 훅으로 감싸고, debouncedSendRequest 함수는 useMemo 훅으로 감싸서 코드를 수정해보았다. 정상적으로 동작하는 것처럼 보인다.
debouncedSendRequest(value) 구문보면 계속해서 value 인자를 주고 있는데 이 부분을 useCallback 의 종속성 인자로 바꾸어 보면, 결국 처음 코드와 같게 된다.
리바운싱할 때마다 디바운스 함수를 생성하지 않게 하는 것이 관건인데 보통 useRef 훅으로 함수를 감싸는 것을 추천한다. 아래와 같은 형태가 되는데 만약 useRef 내부 함수에서 state 값을 참조하면 클로저가 되어버리기 때문에 주의해야 한다.
const ref = useRef(debounce(() => {
// value 가 scope 를 벗어난 외부 변수이기 때문에 초기값으로 세팅된다 (클로저)
console.log(value);
}, 500));
value 상태 값을 항상 최신으로 유지하기 위해 함수를 다시 호출하고 ref 에 다시 할당해야 한다.
(즉, 클로저라는 문제 때문에 value 값이 변경될 때마다, ref.current 값을 교체해주어야 된다.)
enum 열거 타입을 기준으로 집합을 만들고 싶을 때, enum 을 키 값으로 하는 EnumMap 을 사용하는 것을 권장한다.
enum 의 ordinal 함수의 결과 값을 배열의 인덱스로 사용해서 분류하는 것보다 훨씬 안정적이고 간결하다.
static class Plant {
enum LifeCycle { ANNUAL, PERENNIAL, BIENNIAL }
final String name;
final LifeCycle lifeCycle;
public Plant(String name, LifeCycle lifeCycle) {
this.name = name;
this.lifeCycle = lifeCycle;
}
@Override
public String toString() {
return name;
}
}
위와 같이 식물에 대한 클래스가 주어질 때, ANNUAL(한해살이), PERENNIAL(여러해살이), BIENNIAL(두해살이) 를 기준으로 식물들을 분류하고 싶다고 가정하자. 두 가지 방식을 떠올릴 수 있다.
Enum 열거체를 순서대로 표현한 이중 배열
Enum 열거체를 키 값으로 하는 Map
Enum 열거체를 순서대로 표현한 이중 배열은 문제점이 많다. Enum 의 길이는 고정되어 있으므로 배열로 만들텐데 배열은 일전에도 언급하였듯이 제네릭과 호환이 되지 않는다. (비검사 형변환을 해야될 수도 있다.) 또한, 배열은 각 인덱스의 의미를 모르니 출력할 때 레이블을 달아주어야 한다. 아마도 이렇게 구현할 것이다.
Set<Plant>[] plantsByLifeCycle = (Set<Plant>[]) new Set[Plant.LifeCycle.values().length];
for (int i = 0; i < plantsByLifeCycle.length; i++) {
plantsByLifeCycle[i] = new HashSet<>();
}
// ordinal 로 enum 인덱스를 구해서 배열에 hashset 을 삽입
for (Plant p : garden) {
plantsByLifeCycle[p.lifeCycle.ordinal()].add(p);
}
// 배열의 인덱스가 무엇을 뜻하는지 몰라서 values 를 다시 한 번 호출하는 모습
for (int i = 0; i < plantsByLifeCycle.length; i++) {
System.out.printf("%s: %s%n", Plant.LifeCycle.values()[i], plantsByLifeCycle[i]);
}
Enum 열거체를 키 값으로 하는 EnumMap 을 사용하면 Enum 열거체가 변경이 되어도 유연하게 적용할 수 있고 안전하다.
안전하지 않은 형변환도 사용하지 않으면서 열거타입 자체에서 toString 출력용 문자열을 제공하니 출력 결과에 레이블을 달 필요도 없다. 더 나아가 배열 인덱스를 계산하는 과정에서 오류가 날 가능성도 완전봉쇄한다.
Map<Plant.LifeCycle, Set<Plant>> plantsByLifeCycle = new EnumMap<>(Plant.LifeCycle.class);
for (Plant.LifeCycle lc : Plant.LifeCycle.values()) {
plantsByLifeCycle.put(new HashSet<>());
}
for (Plant p : garden) {
plantsByLifeCycle.get(p.lifeCycle).add(p);
}
System.out.println(plantsByLifeCycle);
(Strem 버전)
▼
System.out.println(garden.stream()
.collect(Collectors.groupingBy(p -> p.lifeCycle,
() -> new EnumMap<>(Plant.LifeCycle.class), Collectors.toSet())));
이중으로 Enum 열거체의 값들을 매핑할 때도, EnumMap 으로 관리하면 좋다.
public enum Phase {
SOLID, LIQUID, GAS;
public enum Transition {
MELT(SOLID, LIQUID), FREEZE(LIQUID, SOLID),
BOIL(LIQUID, GAS), CONDENSE(GAS, LIQUID),
SUBLIME(SOLID, GAS), DEPOSIT(GAS, SOLID);
private final Phase from;
private final Phase to;
Transition(Phase from, Phase to) {
this.from = from;
this.to = to;
}
private static final Map<Phase, Map<Phase, Transition>>
m = Stream.of(values()).collect(groupingBy(t -> t.from,
() -> new EnumMap<>(Phase.class),
toMap(t -> t.to, t -> t,
(x, y) -> y, () -> new EnumMap<>(Phase.class))));
public static Transition from(Phase from, Phase to) {
return m.get(from).get(to);
}
}
}
예전에는 열거한 값들을 집합으로 사용할 경우, 서로 다른 2의 거듭제곱 값을 할당한 정수 열거 패턴을 주로 사용했었다.
이렇게 만들어진 집합은 비트 필드라고 부르고, 적은 메모리로 다양한 정보를 담을 수 있어 프로그래밍 문제에서 자주 사용하곤 한다.
public class Text {
public static final int STYLE_BOLD = 1 << 0;
public static final int STYLE_ITALIC = 1 << 1;
public static final int STYLE_UNDERLINE = 1 << 2;
public void applyStyles(int styles) { }
}
하지만 이런 기법은 정수 열거 패턴의 단점을 그대로 지니고, 해석하기가 어렵다. 비트 필드 값을 순회하기에도 까다롭고,
최대 몇 비트가 필요할 지 예상해야 한다. 구현 로직을 변경하지 않고서 비트 수를 더 늘릴 수 없기 때문에 적절한 타입을 선정하는 것도 중요하다.
이제는 java.util.EnumSet 클래스를 사용하자. Set 인터페이스를 구현했으며, 타입 안전하고, EnumSet 내부도 비트 벡터로 구현되어 있기 때문에 깔끔하게 코드를 작성할 수 있다. 비트를 직접 다룰 때 생기는 각종 오류들로부터 해방시키고 구현에 구애받지 않고 개발할 수 있어 생산성도 높다.
public class Text {
public enum Style { BOLD, ITALIC, UNDERLINE, STRIKETHROUGH };
// EnumSet 보다 인터페이스인 Set 을 넘겨 다른 구현체를 넘겼을 때도 처리할 수 있게 하자.
public void applyStyles(Set<Style> styles) {
....
}
}
// 사용부
Text text = new Text();
text.applyStyles(EnumSet.of(Style.BOLD, Style.ITALIC));
EnumSet 이나 EnumMap 과 같이 열거 타입 기반의 자료구조에서 사용하려고 만든 메서드이다. 하지만 이 메서드를 프로그래머가 임의의 메서드에서 사용한다면 오동작할 수 있다.
public enum Ensemble {
SOLO, DUET, TRIO, QUARTET, QUINTET,
SEXTET, SEPTET, OCTET, NONET, DECTET;
// 아래처럼 사용하면 안 된다.
public int numberOfMusicians() { return ordinal() + 1; }
}
상수 선언 순서를 바꾸는 순간 오동작하는 코드이며, 이미 사용 중인 정수와 값이 같은 상수라면 추가할 방법이 없다.
값을 중간에 비워둘 수도 없다. 차라리 아래와 같이 선언과 동시에 인스턴스 필드에 저장하면 된다.
public enum Ensemble {
SOLO(1), DUET(2), TRIO(3), QUARTET(4), QUINTET(5),
SEXTET(6), SEPTET(7), OCTET(8), NONET(9), DECTET(10);
private final int numberOfMusicians;
Ensemble(int size) { this.numberOfMusicians = size; }
public int numberOfMusicians() { return nubmerOfMusicians; }
}
자바에서 열거 타입을 지원하기 전에는 아래와 같이 정수 상수를 한 묶음으로 선언하여 사용하였다.
정수 열거 패턴
public static final int V3_INFO = 0;
public static final int V3_UPDATE = 1;
public static final int V3_SCAN = 2;
public static final int ALYAC_INFO = 0;
public static final int ALYAC_UPDATE = 1;
public static final int ALYAC_SCAN = 2;
하지만 이런 정수 열거 패턴은 아래와 같은 단점들이 있다.
1. 타입 안전을 보장할 방법이 없으며 표현력도 좋지 않다.
정수 열거 패턴을 위한 이름 공간(namespace) 을 지원하지 않기 때문에 같은 상수값을 사용하는 변수들이 모두 같은 값으로 인식될 수 있다. 예를 들어 위 코드에서 V3_INFO 와 ALYAC_INFO 값이 같은 값으로 인식된다. V3 관련 메서드에서 ALYAC 상수 값을 사용해도 컴파일러가 오류/경고 메세지를 출력하지 않는다는 말이다.
또한 이름 공간(namespace) 을 지원하지 않기 때문에 접두사를 붙여 변수 네이밍을 해야한다는 점도 단점이다.
2. 정수 열거 패턴을 사용한 프로그램은 깨지기 쉽다.
평범한 상수를 나열한 것 뿐이라 컴파일하면 해당 값이 클라이언트 파일에 하드코딩된다. 만약 상수의 값이 바뀌면 반드시 다시 컴파일 해서 재배포해야 한다. 다시 컴파일되지 않은 클라이언트 파일이 서버에서 변해버린 상수 값을 받을 때 의도하지 않은 방향으로 동작할 수 있다.
3. 정수 상수는 문자열로 출력하기 어렵다.
public static final int V3_INFO = 0;
System.out.println(V3_INFO); // 문자열이 아닌 의미 없는 상수 출력
그렇다고 문자열 열거 패턴을 사용하면 안 된다.
문자열 값을 하드 코딩하는데 오타가 발생하면 자연스레 런타임 오류가 발생한다. 심지어 문자열 상수들을 비교할 때 성능 저하가 발생한다.
4. 같은 정수 열거 그룹에 속한 모든 상수를 한 바퀴 순회하는 방법도 마땅치 않다.
열거 그룹에 속한 정수 갯수가 총 몇 개인지 알 수 없어 순회하기도 힘들다.
이런 정수 열거 패턴의 단점을 보완하고 여러 장점들을 사용하는 자료구조가열거 타입(Enum Type)이다.
열거 타입
다른 언어와 다르게 자바에서 열거 타입은 클래스이며 사실상 싱글톤 객체이다.
열거 상수 하나당 자신의 인스턴스를 하나씩 만들어 public static final 필드로 공개하는데 외부에서 접근할 수 있는 생성자를 제공하지 않기 때문에 사실상 final class 이며 클라이언트가 인스턴스를 직접 생성하거나 확장할 수 없기 때문이다.
열거 타입 선언으로 만들어진 인스턴스들은 딱 하나씩만 존재한다.
public enum WeekDay {
MONDAY(0),
TUESDAY(1),
WEDNESDAY(2),
THURSDAY(3),
FRIDAY(4),
SATURDAY(5),
SUNDAY(6);
private final int value;
WeekDay(int value) {
this.value = value;
}
}
1. 열거 타입은 컴파일타임 타입 안전성을 제공한다.
public static final int MONDAY = 0;
void test() {
enumTest(MONDAY); // 컴파일 오류
enumTest(WeekDay.MONDAY); // 정상 동작
}
private void enumTest(WeekDay weekDay) {
}
다른 타입의 값을 인자로 받았을 때 컴파일 오류가 발생한다. 타입을 명확히 전달할 수 있다는 강점이 있다.
2. 열거 타입에는 각자의 이름공간(namespace)이 있어서 이름이 같은 상수도 선언할 수 있다.
4. 열거 타입에는 임의의 메소드나 필드를 추가할 수 있고 임의의 인터페이스를 구현하게 할 수도 있다.
public enum WeekDay {
MONDAY(0),
TUESDAY(1),
WEDNESDAY(2),
THURSDAY(3),
FRIDAY(4),
SATURDAY(5),
SUNDAY(6);
//임의의 필드
private final int value;
WeekDay(int value) {
this.value = value;
}
//임의의 메소드
public void test() {
}
}
상수 값들과 연관된 데이터들이나 계산 과정들을 enum 객체 안에다 모두 담을 수 있어 코드 응집력을 높일 수 있다.
참고로 클래스로써 Object 메소드들을 지원하고 Comparable, Serializable 도 구현해두었다.
직접 구현해보면서 테스트해보자.
테스트
public enum Planet {
MERCURY(3.302e+23,2.439e6),
VENUS(4.869e+24,6.052e6),
EARTH(5.975e+24, 6.378e6),
MARS(6.419e+23,3.393e6),
JUPITER(1.899e+27,7.149e7),
SATURN(5.685e+26,6.027e7),
URAUS(8.683e+25,2.556e7),
NEPTUNE(1.024e+26,2.477e7);
private final double mass;
private final double radius;
//표면중력
private final double surfaceGravity;
//중력상수
private static final double G = 6.67300E-11;
Planet(double mass, double radius) {
this.mass = mass;
this.radius = radius;
this.surfaceGravity = G * mass / (radius * radius);
}
public double mass() {
return mass;
}
public double radius() {
return radius;
}
public double surfaceGravity() {
return surfaceGravity;
}
public double surfaceWeight(double mass) {
return mass * surfaceGravity;
}
}
Planet Enum 은 행성들의 질량, 반지름, 표면중력 상수를 가지고 있는 데이터 집합이다.
상수인 질량과 반지름이 주어졌을 때 표면중력 상수 또한 변하지 않는 값으로 계산할 수 있는 상수 값이다.
표면중력도 마찬가지. 질량, 반지름, 표면중력 상수 값들을 토대로 만들어지기 때문에 변하지 않는 상수 값이다. 이와 같이 Enum 은 상수들과 연관된 상수 값들을 연산할 수 있는 메서드를 한 공간에 배치하여 표시할 수 있다는 장점이 있다.
열거 타입은 자신 안에 정의된 상수들을 배열에 담아 반환하는 values() 메소드를 제공한다. 상수들은 선언된 순서대로 저장된다.
for (Planet p : Planet.values()) {
System.out.printf("%s 에서의 무게는 %f 이다. %n", p, p.surfaceWeight(mass));
}
열거 타입의 toString 메소드는 상수 이름을 문자열로 반환한다. 또한 toString 메소드를 재정의하여 사용할 수 있다.
public enum Planet {
// ...중략...
//재정의한 toString, 이름을 소문자로 출력한다.
@Override
public String toString() {
return this.name().toLowerCase();
}
}
열거 타입의 장점은 열거 타입에 선언한 상수 하나를 제거하더라도제거한 상수를 참조하지 않는 클라이언트에는 아무 영향이 없다. 반대로 제거된 상수를 참조한 클라이언트는 컴파일 타임 때 에러가 발생하고 컴파일 하지 않은 클라이언트에서는 런타임 에러가 발생한다.
열거타입의 패턴
위 테스트에서는 단순히 상수 값들을 데이터들과 연관지었지만 만약 열거 타입의 메서드가 상수에 따라 다르게 동작해야 한다면 아래 패턴들을 참고해볼 수 있다.
상수별 메소드 구현
간단하게 if 나 switch 문으로 조건문을 통해 해결할 수 있다. 하지만 이는 안티패턴이다.
새로운 상수가 추가된다면 case 문도 추가해야 한다. 데이터가 추가 될 때 부수적으로 생각해야 하는 로직 변경이 있다면 OCP 원칙에 위배될 수 있다.
public enum Operation {
PLUS,MINUS,TIMES,DIVDE;
public double apply(double x, double y) {
switch (this) {
case PLUS:
return x + y;
case MINUS:
return x - y;
case TIMES:
return x * y;
case DIVDE:
return x / y;
}
throw new AssertionError("알 수 없는 연산:" + this);
}
}
여기서 상수별 메소드 구현을 사용하면 조금 더 나은 방식으로 개선할 수 있다.
상수별 메소드 구현은 열거 타입에 추상 메소드를 선언하고 각 상수별로 클래스 몸체를 자기자신이 재정의하는 방법이다.
public enum Operation {
PLUS("+") {
public double apply(double x, double y) {
return x + y;
}
},
MINUS("-") {
public double apply(double x, double y) {
return x - y;
}
},
TIMES("*") {
public double apply(double x, double y) {
return x * y;
}
},
DIVDE("/") {
public double apply(double x, double y) {
return x / y;
}
};
private final String symbol;
Operation(String symbol) {
this.symbol = symbol;
}
@Override
public String toString() {
return symbol;
}
public abstract double apply(double x, double y);
}
참고로 열거 타입엔 상수 이름을 입력받아 그 이름에 해당하는 상수를 반환해주는 valueOf(String) 메소드가 자동 생성된다.
toString 메소드를 재정의했다면, toString이 반환하는 문자열을 해당 혈거 타입 상수로 변환해주는 fromString 메소드도 함께 제공하는 걸 고려해보자.위의 코드에서 toString 메소드를 재정의해 기존 상수의 이름이 아닌 각 연산자의 기호를 반환하도록 구현하였다. 반대로 fromString 메소드를 구현하여 연산자 기호를 매개변수로 전달하면 알맞은 열거 타입 객체를 반환하도록 해보자
private static final Map<String, Operation> stringToEnum =
Stream.of(Operation.values())
.collect(Collectors.toMap(Operation::toString, operation -> operation));
//Optional로 반환하여 값이 존재하지않을 상황을 클라이언트에게 알린다.
public static Optional<Operation> fromString(String symbol) {
return Optional.ofNullable(stringToEnum.get(symbol));
}
여기서 중요하게 봐야할 것은 Map에 Operation 상수가 추가되는 시점이다. Operation 상수들은 정적 필드가 초기화되는 시점에 추가된다. 열거 타입에서 정적 필드는 열거 타입 상수가 생성된 후에 초기화 된다. 그렇기 때문에 열거 타입 생성자에서 정적 필드를 참조하려고 하면 컴파일 에러가 발생한다.
만약, putString 이라는 메소드를 생성자에서 Map 에 추가하려고 하면 어떻게 될까?
groupingBy 는 Java Stream collect 메서드에서 사용하는 Collector 객체이자 특정 속성(property) 값에 의해서 그룹핑을 짓는 메서드이다. 결과값으로 항상 Map<K, V> 형태를 리턴하며 아래와 같이 최대 3가지 파라미터를 받을 수 있다. 두 가지 인수만 사용된다면 classifier 와 downstream 만 사용한다.
classifier (Function<? super T, ? extends K>): 분류 기준을 정의한 함수
mapFactory (Supplier<M>): 결과 값 Map<K,V> 를 다른 Object 로 맵핑하는 함수
downStream (Collector<? super T,A,D>): 집계 방식을 변경하는 또 다른 Collector 객체로 결과 값 Map<K,V> 에서 V 의 타입을 변경
아래와 같이 Person 타입이 있다고 가정할 때 다양한 groupingBy 예제를 살펴보고 정리한다.
@AllArgsConstructor
@Setter
public static class Person {
private String name;
private String city;
private Integer age;
private PersonJob personJob;
}
public static class PersonTuple {
private String name;
private String city;
public PersonTuple(String name, String city) {
this.name = name;
this.city = city;
}
}
private static List<Person> getPersons() {
return List.of(
new Person("안유진", "서울", 20, PersonJob.ARMY),
new Person("리즈", "서울", 22, PersonJob.STUDENT),
new Person("레이", "도쿄", 19, PersonJob.STUDENT),
new Person("가을", "수원", 18, PersonJob.EMPLOYEE),
new Person("장원영", "수원", 20, PersonJob.POLICE),
new Person("이서", "청주", 18, PersonJob.POLICE)
);
}
단일 키로 그룹핑하기
var result = getPersons().stream().collect(groupingBy(Person::getCity));
Map<String, List<Person>> 객체로 리턴되고, 수원, 서울, 청주, 도쿄 키로 Person 객체로 그룹핑된다.
복합 키로 그룹핑하기
public static class PersonTuple {
private String name;
private String city;
public PersonTuple(String name, String city) {
this.name = name;
this.city = city;
}
}
var result2 = getPersons().stream().collect(groupingBy(person -> new PersonTuple(person.getName(), person.getCity())));
Map<PersonTuple, List<Person>> 객체로 리턴되고, 위에 정의된 Tuple 로 Person 객체가 그룹핑된다.
집계 변경해서 그룹핑하기 (toSet)
var result3 = getPersons().stream().collect(groupingBy(Person::getPersonJob, toSet()));
groupingBy 를 적용했을 때 기본 Value 타입은 리스트다. 위 예제처럼 toSet 로 집계함수를 변경하면,
Map<Person, Set<Person>> 객체로 리턴된다.
집계 변경해서 통계 그룹핑하기 (sum)
단순히 타입을 변경하는 것 이외에 reduce 같은 함수로 통계 데이터를 얻어올 수 있다.
var result4 = getPersons().stream().collect(groupingBy(Person::getPersonJob, summingInt(Person::getAge)));
downStream방식을 summingInt 메서드로 합계를 낸 예제이다. 직업을 기준으로 Person 객체를 그룹핑했을 때 그 객체 나이들을 전부 더해서 산출한다. 리턴 타입은 Map<Person, Integer>> 이다.
Map 의 Value 값을 다른 타입으로 리턴하기
var result5 = getPersons().stream().collect(groupingBy(Person::getPersonJob, mapping(Person::getName, joining(",", "[", "]"))));
groupingBy 의 downStream 을 통해 Map 의 value 값을 다른 타입으로 리턴할 수 있다. 위 처럼 기본 컬렉션 타입은 toSet, toList, toMap, toConcurrentMap, toCollection 으로 static 메서드를 제공하지만 그 이외의 타입은 mapping 메서드를 통해 다른 타입을 변경할 수 있다. mapping(Function<? super T,? extends U> mapper, Collector<? super U,A,R> downstream) 원형을 살펴보면 groupingBy 의 2개 인자를 받는 함수 원형과 같다. 똑같이 Key 를 분류하는 함수와 value 를 집계하기 위한 함수를 제공하면 된다.
Map<PersonJob, String> 객체로 리턴된다. Value 가 집계될 때 "[" "]" 로 감싸서 값들을 , 콤마로 묶는다.
Map 을 다른 타입으로 리턴하기
var result6 = getPersons().stream().collect(groupingBy(Person::getPersonJob, () -> new EnumMap<>(PersonJob.class), toList()));
EnumMap<PersonJob, List<Person>> 객체로 리턴된다. 세 가지 인수를 받을 때는 두 번째 인자가 MapFactory 이고 세 번째 인자가 downstream 이다. mapFactory 가 Supplier 이므로 인자가 없는 함수형 인터페이스를 제공해야 하므로 () -> new 형식으로 새로운 Map 타입으로 리턴하면 된다.
(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다. 이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
l: 왼쪽으로 한 칸 이동 r: 오른쪽으로 한 칸 이동 u: 위쪽으로 한 칸 이동 d: 아래쪽으로 한 칸 이동
출발 위치, 도착 위치, 총 거리 K 가 주어질 때, 미로를 탈출하기 위한 경로를 구하시오.
2.문제예제
문제 지문에 잘 나와있으므로 생략한다.
3.팩트추출
Fact 1: 사전 순으로 출력되려면 항상 d => l => r => u 순으로 탐색해야 한다. 지금 탐색 순서가 실패하면 아래 단계 순번으로 탐색하다가 다시 윗 단계 순번으로 탐색해야 한다.
Fact 2 : 2차원 배열로 구성되어 있는 그래프를 탐색하는데 위와 같이 특정한 조건이 존재하면 DFS 로 탐색하는 것이 좋다.
특정한 조건이란, 모두 비교하지 않고 도착이 가능한 형태인지 체크하는 문제이거나, 체인 형태로 탐색하는 순서(조건 존재)가 있는 경우이다. 해당 문제와 같이 실패했을 때도 탐색하는 순서가 정해져있다면 금상첨화다.
Fact 3 : 가지치기를 할 수 있다. 현재 위치에서 도착 위치까지 남은 거리와 남은 k 가 같은 짝수이거나 홀수이어야 한다. 짝 /홀이 다르다면, 어차피 도착을 못 하기 때문에 더 이상 탐색할 필요가 없다.
4.문제전략
d => l => r => u 순서로 dfs 탐색하고 현재 위치에서 도착 위치까지 남은 거리와 남은 k 거리를 비교한다.
5. 소스코드
import java.util.*;
class Solution {
// d, l, r, u 순으로 탐색
private static final int[] dx = { 1, 0, 0, -1};
private static final int[] dy = { 0, -1, 1, 0};
private static final String[] term = {"d", "l", "r", "u"};
private static int mapX, mapY;
private static int endX, endY;
private String tempAnswer = "";
public boolean dfs(int x, int y, int k, String str, int diff) {
if(k==0 && diff==0){
tempAnswer = str;
return true;
}
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX >=0 && nextY >= 0 && nextX < mapX && nextY < mapY && diff<=k) {
if ((diff % 2 == 0 && k % 2 ==0) || (diff % 2 == 1 && k % 2 ==1)) {
if (dfs(nextX, nextY, k - 1, str + term[i], Math.abs(nextX - endX) + Math.abs(nextY - endY))) {
return true;
}
}
}
}
return false;
}
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer;
mapX = n;
mapY = m;
endX = r-1;
endY = c-1;
int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
dfs(x-1, y-1, k, "", diff);
if(tempAnswer.equals("")){
answer = "impossible";
} else {
answer = tempAnswer;
}
return answer;
}
}
