프로그래머스 - 방의 개수

문제 설명

8가지의 방향 수가 입력으로 주어지고, (0,0)에서 출발하여 방향대로 움직여서 도형을 이루는 개수를 출력하는 문제이다.

도형이 만들어지는 경우는 해당 정점에 이미 다른 노드로부터 방문한 흔적이 있고 새로운 간선이 만들어지는 경우가 도형이 만들어지는 경우이다. (:= 사이클 형성)

주의사항

도형이 만들어지는 경우 엣지케이스가 존재한다.

교차점이 생성될 경우

이러면 도형은 위 아래 삼각형이 만들어지게 되는데 도형이 2개인지 1개인지 판별할 수 없게 된다.

맨 왼쪽 그림에서 해당 a로 다시 들어올때 방문했던 이력이 있고, 새로운 간선이 생겨 도형이 만들어졌다. 하지만 도형이 2개가 만들어 졌는지 1개가 만들어졌는지 알수 없다. 그래서 2배로 확대해서 보면 쉽게 2개가 만들어졌는지 1개가 만들어 졌는지 알 수 있다.

2배율을 하게 되면 중간 점에서 방문했던 이력이 있으니 1번 카운팅 그리고 최종 a지점으로 돌아올때 카운팅 하게 되어 교차점으로 부터 도형이 2개 생성되는 엣지케이스를 통과할 수 있다.

풀이 

class Node{
		int y,x;

		public Node(int y,int x){
			this.y=y;
			this.x=x;
		}

		public boolean equals(Object o){
			Node o1=(Node) o;

			return this.y==o1.y && this.x == o1.x;
		}

		public int hashCode(){
			return Objects.hash(y,x);
		}
	}
	int dy[]={-1,-1,0,1,1,1,0,-1},dx[]={0,1,1,1,0,-1,-1,-1};

	/**
	 * 2배율 := 스케일 아웃 하여 재방문 counting 처리
	 *
	 */
	public int solution(int[] arrows) {
		int answer = 0;
		Node cur=new Node(0,0);
		Map<Node,List<Node>> v=new HashMap<>();

		for(int dir: arrows){
			int repeat=2;
			while(repeat-->0){
				Node next=new Node(cur.y+dy[dir],cur.x+dx[dir]);
				if(!v.containsKey(next)){ // 처음 방문
					List<Node> edges=new ArrayList<>();
					edges.add(cur);
					v.put(next, edges);

					if(v.get(cur)==null){
						List<Node> edges2=new ArrayList<>();
						edges2.add(next);
						v.put(cur,edges2);
					}else{
						v.get(cur).add(next);
					}
				}else if(v.containsKey(next) && !v.get(next).contains(cur)){
					// next 정점에 이미 다른 노드가 도달한 이력이 있으며 새로운 간선이 생기는 경우 := 도형이 만들어지는 경우
					v.get(next).add(cur);
					v.get(cur).add(next);
					answer++; //도형 생성
				}

				cur= next;
			}
		}
		return answer;
	}