[프로그래머스] level2. 방문 길이 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 방문 길이 (자바 JAVA)

 

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

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

---

# 접근 방법 및 풀이 

 

• 처음에 무심코 풀고 8번부터 실패 떠서 당황했던 문제다.
• 8번부터 실패가 뜬다면 "UDU" = 1인 경우를 떠올려보자!
• 먼저, 좌표평면을 2차원 배열 형태로 생각해서 풀었다. 범위가 -5~5 이므로 칸의 개념으로 바꿔주면, map[11][11] 형태 2차원 배열로 표현이 가능하다.
• 그리고 한번 간 길은 다시 지나갈 경우 갯수를 세면 안되기 때문에 visit[][]배열을 만들었다.
• 처음엔 단순히 이미 방문 체크한 칸을 또 방문하면 안되는걸로 생각해서 visit[][] 2차원 배열로 만들었는데, 뒤늦게 해당 칸 방문시 어느방향에서 오는지를 체크해야한다는 것을 깨달았다.

• 	↓
  →	1, 1	←
  	↑

• 예를들어, (1,1) 칸으로 간다고 했을 때 다음과 같이 상하좌우 4방향에서 길을 만들어 올 수 있고, 다 각각 다른 길이기 때문에 visit배열을 visit[11][11][4]인 3차원 형태로 만들어야한다.
• 그리고 방문하지 않은 visit[][][] 일 경우 방문체크해주고 answer++을 시켜주었다.
• 여기까지 생각하고 그대로 구현했는데 8번부터 쭉 틀렸다. 띠용..?
• 여기서 뭐가 틀렸는지 스스로 반례를 구해서 해결했으면 다행이지만, 생각이 안나서 질문하기 찾아봤다.
• 나같이 8번부터 틀린 사람이 많았고, "UDU" = 1이라는 반례를 찾았다.
• 현재 내가 짰던 코드는 답이 2가 나왔고, 가장 중요한 것은 왕복까지 처리해줘야 한다는 것이다. 즉, 다시 되돌아올 경우 처리도 해야한다.
• 예를들어 현재위치는 r, c 다음 갈 위치는 nr, nc, 방향은 d라고 가정해보자.
• visit[nr][nc][d]을 방문하지 않았다면 visit[nr][nc][d] = true를 해준다.
• 그리고 현재 위치 r,c에서 d의 반대방향인 곳도 visit체크를 해주어야한다. visit[r][c][현재 d의 반대방향] = true;
• 그래야 되돌아올 경우 이미 방문체크를 했기때문에 카운팅을 해주지 않는다.
• 자세한건 코드참고

# 주의할 점 

 

• 8번부터 안된다면 "UDU" 했을 경우 답은 1임.

 

JAVA 코드

class Solution {
    static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, -1, 0, 1 };
	public static int solution(String dirs) {
		int answer = 0;
		int map[][] = new int[11][11];
		boolean visit[][][] = new boolean[11][11][4];
		int r = 5, c = 5;
		for (int i = 0; i < dirs.length(); i++) {
			char cc = dirs.charAt(i);
			int d = 0;
			if (cc == 'U')
				d = 0;
			if (cc == 'L')
				d = 1;
			if (cc == 'D')
				d = 2;
			if (cc == 'R')
				d = 3;
			int nr = r + dr[d];
			int nc = c + dc[d];
			if (nr < 0 || nc < 0 || nr >= 11 || nc >= 11)
				continue;
			if (!visit[nr][nc][d]) {
				visit[nr][nc][d] = true;
				d = (d%2 == 0)? 2-d: 4-d;
				visit[r][c][d] = true;
				answer++;
			}
			r = nr;
			c = nc;
		}
		System.out.println(answer);
		return answer;
	}
}

 

 

REVIEW