[프로그래머스] 방의 개수 - JAVA

🔗 문제

 

👨🏻‍💻 풀이 및 코드

 

접근 방법

사방이 막힌 도형이 만들어지는 조건은 이미 한번 방문한 점을 다시 방문한다면 도형이 만들어진다.

그림에서 빨간색 점을 방문했던 점이라고 한다면 마지막 빨간색 선, 즉 방문했던 점을 다시 방문했을 때 도형이 만들어진다.

 

 

단, 이미 그어진 선을 다시 잇는 경우는 안된다. 

한 번 그어진 선을 다시 긋는 경우 (1)

 

한 번 그어진 선을 다시 긋는 경우 (2)

즉, 이미 이어진 선인지 체크해야 한다.

 

추가로 주의해야할 점은 대각선 체크를 위해 이동할 때 두 칸씩 이동해야 한다.

해당 그림처럼 이동했다면 삼각형이 하나 만들어지지만 위의 접근방식으론 갯수를 셀 수 없다. 

같은 이동을 두 칸씩으로 바꾸면 대각선 경우의 도형의 갯수도 셀 수 있다.

 

정리

입력에서 주어진 방향대로 점을 이동시키면서, 이미 방문했던 점이고 처음 잇는 선이라면 도형의 갯수를 증가시킨다.

대각선 체크를 위해 두 칸씩 이동시킨다.

 

 

전체 코드 1 . Set 사용

import java.util.*;

class Solution {
    int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    public int solution(int[] arrows) {
        int answer = 0;
        int o1x=0, o1y=0;
        // 점 방문 여부 체크
        Set<String> visited = new HashSet<>();
        // 선 중복 체크
        Set<String> line = new HashSet<>();
        visited.add(new String(o1x + " " + o1y));
        
        for(int arrow : arrows) {
            for(int i=0; i<2; i++) {
                int o2x = o1x + dx[arrow];
                int o2y = o1y + dy[arrow];

                String point1 = new String(o1x + " " + o1y);
                String point2 = new String(o2x + " " + o2y);
                if(visited.contains(point2) && !line.contains(new String(point1+point2))) {  // 방문한 점이고 이어진적 없는 선이라면
                    answer++;
                } 
                visited.add(point2);
                line.add(point1+point2);
                line.add(point2+point1);

                o1x = o2x; o1y = o2y;
            }
            
        }
        
        return answer;
    }
}

 

 

참고

1. new String(o1x + " " + o1y)

• 점 방문 여부 체크 용도로 Set<String> visited = new HashSet<>() 을 사용했다.
• 좌표를 String 으로 바꿔 (new String(o1x + " " + o1y)) set에 삽입했다. 처음에 new String(o1x + "" + o1y) 으로 했다가 틀렸다. 다시 생각해보니 ""인 경우엔 x=1, y=12 일 때와 x=12, y=2 를 String으로 변환했을 때의 값이 같아 구분이 가지 않아 틀렸다는 걸 알게 됐다. 스터디원이 찾아준 덕분에 해결할 수 있었다.

 

2. Set.contains(new String()) → True??

String s1 = "12";
String s2 = new String("12");
String s3 = "12";
String s4 = new String("34");

• s1 == s3  → True
• s2 == s4  →  False

자바에서 String을 비교할 때 new String 으로 객체를 생성한 경우에는 == 로는 false가 나온다. (equals 를 사용해야 True)

 

Set을 사용한 경우는 어떨까?

Set<String> st = new HashSet<>();
String s2 = new String("12");
st.add(s2);
System.out.println(st.contains(new String("12")));  → True

 

Set에 new String으로 생성한 객체를 삽입했다. 그 후 Set에 해당 객체가 포함되어 있는지 판단할 때 new String 으로 해도 결과값은 True가 나온다.

 

 

 

전체 코드 2 . Map 사용

import java.util.*;


/*
이미 방문한 점을 다시 방문하면 공간이 생긴다. 단, 이미 그어진 선분을 다시 긋는건 제외
*/
class Solution {
    int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    class Node {
        int x, y;
        
        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);
        }
    }
    
    public int solution(int[] arrows) {
        int answer = 0;
        Map<Node, List<Node>> mp = new HashMap<>();     // 키: 방문한 좌표, 값: 해당 좌표에서 이어진 좌표
        int x=0, y=0;
        mp.put(new Node(x,y), new ArrayList<Node>());
        
        for(int arrow : arrows) {       // 이동한 방향
            for(int i=0; i<2; i++) {    // 대각선 체크를 위해 두칸 이동
                int nx = x + dx[arrow];
                int ny = y + dy[arrow];
                
                Node now = new Node(x, y);
                Node next = new Node(nx, ny);
                if(!mp.containsKey(next)) {    // 방문하지 않은 좌표
                    // 연결하기
                    mp.put(next, createList(now));
                    mp.get(now).add(next);
                } else if(!mp.get(next).contains(now)) {    // 방문한 좌표이고 처음 이어진 선
                    answer++;
                    
                    //연결하기
                    mp.get(next).add(now);
                    mp.get(now).add(next);
                }
                
                x = nx; y = ny;
            }
        }
        
        
        return answer;
    }
    
    public ArrayList<Node> createList(Node node) {
        ArrayList<Node> list = new ArrayList<>();
        list.add(node);
        return list;
    }
}

 

참고

1. Map.containsKey(new Node()) → False??

• String과 달리 직접 만든 객체 클래스인 경우 Map에 넣을 때 new Node(x,y) 로 넣고 찾을 때 mp.containsKey(new Node(x, y)) 로 찾는다면 False가 나온다.
• 이유는 객체의 값을 비교하는게 아니라 주소값을 비교하기 때문이다.
• 해결방법은 Node 클래스를 만들 때 다음 두 메서드를 Override 해야 한다.
  
  

class Node {
        ...
        
        @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);
        }
    }