Lv2. 방문 길이

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

1. 풀이 설명

1. "지나가 본 길을 어떻게 저장할지" 가 중요한 문제다.

2. 출발점인 (0,0) 을 visited[5][5] 위치로 설정했다.
   점 사이를 거리로 보고, 각 위치의 점은 4개의 False 로 초기화한 아이템을 갖는 list 값을 갖는다.
   list는 방문 여부에 대한 flag 이다. (오른쪽에서 방문, 아래에서 방문, 왼쪽에서 방문, 위에서 방문)
   예를 들어, 출발점인 (5,5)는 visited[5][5] 이고, visited[5][5] = [False, False, False, False] 로 초기화 되어있다.

(6,4)  (6,5)  (6,6) 
-----------------
|  		|		|
-----------------
(5,4)  (5,5)  (5,6)

3. dirs 를 for문 돌면서, index 가능여부를 체크를 하고 이동이 가능하다면,
   3-1.d에 맞게 이동을 시킨다.
   3-2. 방문한 적이 없다면, 방문 체크를 한 후에 answer +1 을 해준다.
   (이동 후의 점에 해당하는 거리와 이동 전 점에 해당하는 거리의 방문 여부를 모두 True 로 변경한다.)

ex) (3,5) 위치에서 d 가 "U" 라면
y 는 4가 되고 (3,5) 에서 (4,5) 로 이동하는 것이기 때문에
visited[4][5][1] = True # (4,5) 의 아래에서 방문 여부 True 
visited[3][5][3] = True # (3,5) 의 위에서 방문 여부 True

2. 나의 풀이

python

def solution(dirs):
    answer = 0
    
    # R, D, L, U
    visited = [[[False, False, False, False]  for _ in range(11)] for _ in range(11)]
    y, x = 5, 5
    
    for d in dirs:
        if d == "U":
            if 0 <= y < 10:
                y += 1
                if not visited[y][x][1] and not visited[y-1][x][3]:
                    visited[y][x][1] = True
                    visited[y-1][x][3] = True
                    answer += 1
        elif d == "D":
            if 0 < y <= 10:
                y -= 1
                if not visited[y][x][3] and not visited[y+1][x][1]:
                    visited[y][x][3] = True
                    visited[y+1][x][1] = True
                    answer += 1
        elif d == "R":
            if 0 <= x < 10:
                x += 1
                if not visited[y][x][2] and not visited[y][x-1][0]:
                    visited[y][x][2] = True
                    visited[y][x-1][0] = True
                    answer += 1
        else:
            if 0 < x <= 10:
                x -= 1
                if not visited[y][x][0] and not visited[y][x+1][2]:
                    visited[y][x][0] = True
                    visited[y][x+1][2] = True
                    answer += 1
    return answer