방문 길이 (프로그래머스, Lv 3, 스킬체크, Java)

1. 방문 길이

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이 | 프로그래머스

알고리즘 설명:

방문 체크를 할 수 있는 자료구조가 핵심

• 배열 인덱스를 좌표로 활용하기 위해 0,0을 5,5(처음 위치)로 생각

• 한 좌표에 연결되어 있는 4개 좌표 사이 길을 지나갔는지 여부를 체크하기 위해 Visit 클래스를 만듦

  • Visit 멤버 변수로 2차원 배열 link를 만들어 좌표 사이 길을 지나갔는지 체크

• Visit 클래스를 2차원 배열로 만들어 현재 좌표를 관리하고 Visit 맴버변수 link를 통해 지나갔는 지 여부를 관리

• 입력된 커맨드를 switch를 사용하여 현재 위치와 지나감 여부를 업데이트

 

코드(Java):

class Solution {
    public int solution(String dirs) {
		int[] nowPos = { 5, 5 };
		int commandCount = dirs.length();
		int answer =0;
		Visit[][] isVisit = new Visit[11][11];
		for(int i=0;i<11;i++) {
			for(int j=0;j<11;j++) {
				isVisit[i][j] = new Visit();
			}
		}
		
		for (int i = 0; i < commandCount; i++) {
			switch (dirs.charAt(i)) {
			case 'U':
				if (nowPos[1] < 10) {
					if(!isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]][nowPos[1]+1]) {
						answer++;
						isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]][nowPos[1]+1]=true;
						isVisit[nowPos[0]][nowPos[1]+1].link[nowPos[0]][nowPos[1]]=true;
					}
					nowPos[1]++;
				}
				break;
			case 'D':
				if (nowPos[1] > 0) {
					if(!isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]][nowPos[1]-1]) {
						answer++;
						isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]][nowPos[1]-1]=true;
						isVisit[nowPos[0]][nowPos[1]-1].link[nowPos[0]][nowPos[1]]=true;
					}
					nowPos[1]--;
				}

				break;
			case 'R':
				if (nowPos[0] < 10) {
					if(!isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]+1][nowPos[1]]) {
						answer++;
						isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]+1][nowPos[1]]=true;
						isVisit[nowPos[0]+1][nowPos[1]].link[nowPos[0]][nowPos[1]]=true;
					}
					nowPos[0]++;
				}
				break;
			case 'L':
				if (nowPos[0] > 0) {
					if(!isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]-1][nowPos[1]]) {
						answer++;
						isVisit[nowPos[0]][nowPos[1]].link[nowPos[0]-1][nowPos[1]]=true;
						isVisit[nowPos[0]-1][nowPos[1]].link[nowPos[0]][nowPos[1]]=true;
					}
					nowPos[0]--;
				}
				break;
			}

		}
		return answer;
	}
    	public class Visit{
		boolean[][] link;
		public Visit() {
			link = new boolean[11][11];
		}
	}

}