[그래프] 방의 개수 - Java코드 ★★★★★ 매우 어려움

https://programmers.co.kr/learn/courses/30/lessons/49190?language=java 

코딩테스트 연습 - 방의 개수

 

 

문제

 

 

설계

 

오랫동안 생각해보면서 설계에 결론을 내렸다.

 

1. (0,0)에서 계속적인 좌표값이 반드시 필요하다.

2. 어디로 이동했는지에 대한 방향정보가 필요하다. (방향정보를 저장하지않더라도, 다음좌표에대한 연결정보가 필요)

3. 새로운 간선으로 좌표에 두번째 접근시, 방이 생긴다! (HashSet에 지나가는좌표를 저장해줘야 함)

+ 위에 세가지가 핵심이지만, 대각선에 대해서도 생각을 해야한다.

 

   뱀처럼 끊어지지않고 연결된 선이 대각선으로 교차하는 시점에 3번조건과 별개로 반드시 도형이 생긴다.

// 테스트케이스 3번에 집중
int [] arrows = {6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0}; //result = 3
int [] arrows = {6, 2, 4, 0, 5, 0, 6, 4, 2, 4, 2, 0}; //result = 3
int [] arrows = {5, 2, 7, 1, 6, 3}; //result = 3

 테스트 케이스 3번을 집중해서 그려보면, 대각선에 대해서도 코딩이 필요하다는것을 알 수 있다. (젠장!)

 

풀이

클래스 이름이 뭐같지만, 

Point라는 클래스를 정의해 x,y 좌표값과 진행방향 z에 대한 정보를 Set에 저장할것이다. (from, to 를 쌍으로 저장)

Node라는 클래스를 정의해, 이미 지나간 좌표 x,y에 대한 정보를 기록한다.

 

또한 HashSet에서 해당 객체에 존재 여부 Contains 메소드를 사용하기 위해서는

Equals, HashCode값에 대한 오버라이딩이 필요하다.

 

import java.util.HashSet;
class Solution {
    	static class Point{
		int x,y,z;
		Point(int x, int y,int z){
			this.x = x;
			this.y = y;
			this.z = z;
		}
		@Override
		public boolean equals(Object obj) {
			Point p = (Point) obj;
			if(this.x == p.x && this.y == p.y && this.z == p.z)
				return true;
			else
				return false;
		}
		@Override
	    public int hashCode(){
	        int prime = 31;
	        int hashcode = 1;

	        hashcode = prime * hashcode + this.x;
	        hashcode = prime * hashcode + this.y;
	        hashcode = prime * hashcode + this.z;

	        return hashcode;
	    }
	}
	static class Node{
		int x,y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public boolean equals(Object obj) {
			Node p = (Node) obj;
			if(this.x == p.x && this.y == p.y)
				return true;
			else
				return false;
		}
		@Override
	    public int hashCode(){
	        int prime = 31;
	        int hashcode = 1;
	        hashcode = prime * hashcode + this.x;
	        hashcode = prime * hashcode + this.y;
	        return hashcode;
	    }
	}
	public static int solution(int[] arrows) {
    	    	// 값에 따른 좌표 이동 값
    	int[] dx = {0,1,1,1,0,-1,-1,-1};
    	int[] dy = {1,1,0,-1,-1,-1,0,1};
    	int[] dz = {4,5,6,7,0,1,2,3};
    	int x1=0,y1=0,ans=0;
    	int x2,y2;
    	HashSet<Point> set = new HashSet<>();
    	HashSet<Node> node = new HashSet<>();
    	node.add(new Node(x1,y1));
    	for(int z : arrows) {
    		x2=x1+dx[z];
    		y2=y1+dy[z];
    		Point p1 = new Point(x1,y1,z);
    		Point p2 = new Point(x2,y2,dz[z]);
    		if(!set.contains(p1)) {	// 지나간적 없으면 set에 양쪽노드에 대해 저장
    			set.add(p1);
    			set.add(p2);
        		// 지나간적없는 길인데, 다시 노드에 접근한거라면 , 도형이 만들어지므로 ans+1 
    			if(node.contains(new Node(x2,y2))) {
            		//System.out.println("존재 : "+x2 +" "+y2);
    				ans+=1;
        		}
    			// 그게 아니면 새롭게 접근한 좌표이므로 추가
    			else {
    				node.add(new Node(x2,y2));
            		//System.out.println("없음 : "+x2+" "+y2);
    			}
    			
    			// (중요!) 신규 포인트가 대각선으로 그어졌는데, 기존꺼와 교차되었다면, 도형이 만들어지므로 ans+1
    			if(z%2==1) { // 대각이동체크
    				Point x;
    				switch(z) {
    				case 1:
    					x = new Point(x1,y1+1,3);
    					break;
    				case 3:
    					x = new Point(x1,y1-1,1);
    					break;
    				case 5:
    					x = new Point(x1,y1-1,7);
    					break;
    				case 7:
    					x = new Point(x1,y1+1,5);
    					break;
    				default:
    					x = new Point(0,0,0);
    				}					 				
    				if(set.contains(x))
						ans+=1;    				
    			}
    		}
    		x1=x2;
    		y1=y2;
    	}
    	return ans;
    }
}

도형이 생기는 2가지에 Case 에 대해서 Solution함수내에 주석으로 설명해 두었다.

대각선 이동은 z값이 1,3,5,7을 가지는 경우이므로, !z%2==0 으로 홀수검사를 해주었다.

 

HashSet에서 객체의 동일함을 비교하기 위해서는 반드시 equals와 hashCode를 재정의 해주어야 합니다.

아래 글을 참고

https://nesoy.github.io/articles/2018-06/Java-equals-hashcode

Java equals()와 hashCode()에 대해

 풀이 참조 https://ziyuun.tistory.com/5