프로그래머스 : 방문 길이 (Java)

 

🔗 문제 링크

코딩테스트 연습 - 방문 길이

---

---

📖 풀이 과정

- 그래프 관련 유형의 구현 문제입니다.
- 먼저, 단순히 문제를 풀려고만 하다보니 중복되는 부분도 많고, 깔끔하지 않습니다. 그렇기에 흐름?만 보시면 충분할 것 같습니다.
- 중복되지 않고 방문한 곳의 최대 길이를 찾아야 합니다. 
- visited 배열은 4차원으로 만들어 현재 위치의 (x,y)와 이동해야할 곳의 (x,y)에 대해서 구분 지을 수 있도록 했습니다.
- switch문을 통해 입력받는 알파벳에따라 각 해당하는 명령문을 수행하도록 했습니다.
  - 중복되는 부분이 여기서 발생하는데 해당 부분의 마지막에 중복을 없애도록 작성할 수 있을 것 같습니다.
- isIn()메소드를 통해 범위 내부에 있는지 확인합니다.
  - x의 범위는 -5 이상, 5 이하이기 때문에 0에서 10으로 범위를 설정했습니다.
  - 시작 범위는 문제에서 (0,0)이기에 저는 (5,5)로 설정했습니다.

 

 

---

💻 코드

class Solution {
	public int solution(String dirs) {
		int[][] arr = new int[11][11];
		boolean[][][][] visited = new boolean[11][11][11][11];
		char[] dirsArr= dirs.toCharArray();
		int count = 0;
		Point now = new Point(5,5);
		
		for(char str : dirsArr){
			switch(str){
				case 'U' :
					if(!isIn(now.x,now.y + 1)){
						continue;
					}
					if(isValid(visited, now.x,now.y,now.x,now.y + 1)){
						count += 1;
					}
					visited[now.x][now.y][now.x][now.y + 1] = true;
					visited[now.x][now.y + 1][now.x][now.y] = true;
					now.y += 1;
					break;
				
				case 'D' :
					if(!isIn(now.x, now.y - 1)){
						continue;
					}
					if(isValid(visited, now.x,now.y,now.x,now.y - 1)){
						count += 1;
					}
					visited[now.x][now.y][now.x][now.y - 1] = true;
					visited[now.x][now.y - 1][now.x][now.y] = true;
					now.y -= 1;
					break;
				
				case 'R' :
					if(!isIn(now.x + 1, now.y)){
						continue;
					}
					if(isValid(visited, now.x,now.y,now.x + 1, now.y)){
						count += 1;
					}
					visited[now.x][now.y][now.x + 1][now.y] = true;
					visited[now.x + 1][now.y][now.x][now.y] = true;
					now.x += 1;
					break;
				
				case 'L' :
					if(!isIn(now.x - 1, now.y)){
						continue;
					}
					if(isValid(visited, now.x,now.y,now.x - 1, now.y)){
						count += 1;
					}
					visited[now.x][now.y][now.x - 1][now.y] = true;
					visited[now.x - 1][now.y][now.x][now.y] = true;
					now.x -= 1;
					break;
			}
		}
		return count;
	}
	
	private static boolean isValid(boolean[][][][] visited, int x1, int y1, int x2, int y2){
		if(visited[x1][y1][x2][y2] == true && visited[x2][y2][x1][y1] == true){
			return false;
		}
		return true;
	}
	
	private static boolean isIn(int x, int y){
		if(x < 0 || y < 0 || x > 10 || y > 10){
			return false;
		}
		return true;
	}
	
	static class Point{
		int x,y;
		
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}