[자바 코테대비] 거리두기 확인하기

안녕하세요, 오늘은 프로그래머스의 거리두기 확인하기라는 문제에서
제 코드와 '프로그래머스 코딩테스트 문제풀이 전략'이라는 책 속의 코드를 비교하여 개선점을 찾고
스스로 성찰해보는 시간을 갖고자 합니다.

전체코드

제 풀이코드입니다.

import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


class Solution {
	
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, 1, 0, -1};
	public static boolean flag = false;
	
	public static boolean isRange(int x, int y) {
		if(x < 0 || x >= 5 || y < 0 || y >= 5) {
			return false;
		}
		return true;
	}
	
	public static void manhattanDistance(String[] place, int x, int y, int distance, boolean[][] visited) {
		
		for(int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			int afterDistance = distance + 1;
			
			if(isRange(newX, newY) && !visited[newX][newY]) {
				if((afterDistance == 1 || afterDistance == 2) && place[newX].charAt(newY) == 'P') {
					flag = true;
					return;
				}
				
				if((afterDistance == 1) && place[newX].charAt(newY) == 'O') {
					visited[newX][newY] = true;
					manhattanDistance(place, newX, newY, distance+1, visited);
				}
			}
			
		}
	}
	
	public static int checkMap(String[] place) {
		
		
		for(int x = 0; x < 5; x++) {
			for(int y = 0; y < 5; y++) {
				
				if(place[x].charAt(y) == 'P') {
					boolean[][] visited = new boolean[5][5];
					visited[x][y] = true;
					manhattanDistance(place, x, y, 0, visited);
					if(flag) {
						flag = false;
						return 0;
					}
				}
				
			}
		}
		return 1;
	}
	
    public int[] solution(String[][] places) {
        int[] result = new int[5];
    	for(int i = 0; i < 5; i++) {
    		result[i] = checkMap(places[i]);
    	}
    	return result;
    }
}

풀이

접근법

1. dx dy를 사용하여 맨하탄 거리가 2가 될 때까지 모두 방문해본다.
2. 이때 visited 라는 2차원 배열을 사용해서 p가 시작된 곳과 방문한 곳은 체크를 하여 중복방문하는 것을 막는다.
3. 만약 맨하탄 거리 2이내에 p가 2라면 1을 리턴한다.

위 방식으로 이번 문제에 접근했습니다.

그렇다면 이번에는 책의 해설을 참고하여 비교해보겠습니다.

책의 해설에서는 제가 사용했던 visited라는 배열을 사용하지 않았습니다. 그렇다면 방문했던 위치를 중복 방문하지 않도록 어떻게 제어 했을까요?

private boolean isNextToVolunteer(char[][] room, int x, int y, int exclude) {
	for(int d = 0; d < 4; d++) {
    	if(d == exclude) continue;
    
      	int nx = x + dx[d];
      	int ny = y + dy[d];
        if( ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;
        if( room[ny][nx] == 'P') return true;
	}
    return false;

}

아 파라미터로 int exclude 라는 값을 전해서 상 좌 우 하 중 시작했던 방향은 배제하도록 구성했네요.
확실히 이렇게 하면 메모리 낭비를 막을 수 있겠습니다.

또한 저처럼 distance라는 값으로 맨하탄 거리가 1인 경우와 2인 경우를 체크하지 않고
맨하탄 거리가 1인 경우의 탐색과 맨하탄 거리가 2인 경우의 탐색 메소드를 분리했습니다.

이렇게 하니 복잡한 코드를 깔끔하고 가독성있게 작성할 수 있겠네요