[프로그래머스(Lv.5) : JAVA] 방의 개수
1. 문제
(0, 0) 좌표에서 시작해 각 숫자별로 다음과 같은 방향으로 이동합니다.
0이면 위로 이동, 1이면 대각선 위로 이동, 2면 우측으로 이동 ... 이런 식입니다.
이동하는 방향이 담긴 배열이 주어졌을 때, 생성되는 방의 갯수를 return 하도록 solution 함수를 작성하세요. (방: 사방이 막혀있는 것)
제한사항
- 방향이 담긴 배열의 크기 x는 1 <= x <= 100,000 입니다.
- 배열의 원소는 0 이상 7 이하입니다.
- 방은 다른 방으로 둘러 싸여질 수 있습니다.
2. 풀이
우선 좌표를 담을 자료구조가 필요합니다.
보통 (0, 0) 좌표는 arr[0][0], (1, 0) 좌표는 arr[0][1] 처럼 2차원 배열을 이용하는데, 해당 문제는 이렇게 미리 2차원 배열을 선언해둘 수 없습니다. 입력으로 주어지는 배열의 크기가 최대 10만이기 때문에 (0, 0) 좌표를 기준으로 6(좌측이동)만 10만개 주어지면 (-100000, 0) 좌표가 되고, 2(우측이동)만 10만개 주어지면 (100000, 0) 좌표가 되기 때문에 미리 선언해야될 배열의 크기가 200,001 * 200,001 이 되기 때문입니다.
저는 Map 을 사용했고, key로 x, y 좌표를 담은 Node 클래스, value로 해당 좌표와 연결되는 좌표들의 리스트 즉, 간선의 정보를 담았습니다.
Map<Node, List<Node>> map = new HashMap<>();
class Node {
int x, y;
}다음으로 방이 생성되는 조건입니다.
방이 생성되기 위해선 다음 두 가지 조건을 모두 만족해야 합니다.
- 이전에 방문했었던 정점이어야 한다.
- 해당 간선이 처음 생성되는 것이어야 한다.
마지막으로 교차점에 대한 처리입니다.
입력으로 주어지는 배열의 값이 [2, 5, 2, 7] 라고 해보겠습니다.
위 로직대로라면 방이 1개 생성되어야 합니다. 하지만, 실제로는 방이 2개 생성되었습니다. 이는 교차점 때문입니다.
1칸의 이동을 2칸에 대응되도록 움직여준다면 이를 해결할 수 있습니다.
3. 코드
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arrows;
arrows = new int[]{6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0};
System.out.println(solution(arrows)); // 답: 3
}
public static int solution(int[] arrows) {
int answer = 0;
int[] dx = { 0, 1, 1, 1, 0, -1, -1, -1};
int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
Node curNode = new Node(0, 0);
// 방문 여부 관련 선언
// key = 시작 node의 hashcode, value = 연결된 node들의 hashcode
Map<Node, List<Node>> visited = new HashMap<>();
for (int arrow : arrows) {
for (int i = 0; i <= 1; i++) { // 교차점 처리를 위한 스케일업
Node nextNode = new Node(curNode.x + dx[arrow], curNode.y + dy[arrow]);
// 처음 방문하는 경우 = map에 키값이 없는 경우
if (!visited.containsKey(nextNode)) {
// 리스트에 연결점 추가
visited.put(nextNode, makeEdgeList(curNode));
if (visited.get(curNode) == null) {
visited.put(curNode, makeEdgeList(nextNode));
} else {
visited.get(curNode).add(nextNode);
}
// 해당 정점을 재방문했고, 간선을 처음 통과하는 경우
} else if (!visited.get(nextNode).contains(curNode)) {
visited.get(nextNode).add(curNode);
visited.get(curNode).add(nextNode);
answer++;
}
// 이동 완료
curNode = nextNode;
}
}
return answer;
}
private static List<Node> makeEdgeList(Node node) {
List<Node> edge = new ArrayList<>();
edge.add(node);
return edge;
}
private static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return x == node.x && y == node.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
}