[프로그래머스|파이썬] 방문 길이 (Summer/Winter Coding(~2018)/lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

 

🐍파이썬

def solution(dirs):
    answer = 0
    board = [[0 for _ in range(10)] for _ in range(10)]
    dic = {"U":(0, -1), "D":(0, 1), "R":(1, 0), "L":(-1, 0)}
    x, y = 0, 0
    xydic = {}
    
    for command in dirs:
        nx = x + dic[command][0]
        ny = y + dic[command][1]
        #벽면에 부딪친 경우 명령을 무시한다.
        if nx >= 10 or ny >= 10 or nx < 0 or ny < 0:
            continue
            
        if board[ny][nx] == 0:  #아무도 방문한 적 없는 좌표
            answer += 1
            board[ny][nx] = 1   #방문체크
        elif board[ny][nx] == 1:  #누군가 방문한 적 있는 좌표
            if (y, x) not in xydic[(ny, nx)]: #방문한 적 없는 경로
                answer += 1
                
        #방문 경로 저장(x, y <-> nx, ny)
        if (y, x) not in xydic.keys():
            xydic[(y, x)] = set()
        if (ny, nx) not in xydic.keys():
            xydic[(ny, nx)] = set()
        xydic[(y, x)].add((ny, nx))
        xydic[(ny, nx)].add((y, x))
        x, y = nx, ny   #현재 위치를 이동한 좌표로 변경
    # print(xydic)
    # print(board)
    return answer

주어진 테케는 맞는데 히든테케 2개인가 3개 빼고 모두 fail...

def solution(dirs):
    dic = {"U":(0, -1), "D":(0, 1), "R":(1, 0), "L":(-1, 0)}
    x, y = 0, 0
    xyset = set()
    
    for command in dirs:
        nx = x + dic[command][0]
        ny = y + dic[command][1]
        #벽면에 부딪친 경우 명령을 무시한다.
        if nx > 5 or ny > 5 or nx < -5 or ny < -5:
            continue
        xyset.add((y, x, ny, nx))   #start, end
        xyset.add((ny, nx, y, x))   #end, start
        x, y = nx, ny   #현재 위치를 이동한 좌표로 변경
    return len(xyset)//2

좌표(0,0) 에서 시작해 명령어에 따라 바뀌는 x, y 좌표를 nx, ny 좌표라고 하였다.

문제에서 주어진 좌표평면의 경계거 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)이므로, 해당 범위를 벗어나면 명령을 무시하도록 continue를 사용해 아래 코드를 실행하지 않도록 한다. 

이후 xyset이라는 set 자료구조에 시작좌표, 도착좌표를 순서대로 넣고 반대로 도착좌표, 시작좌표도 넣어준다. (이유👉 예를 들어, 1----2를 방문할 때, 1, 2 순서로 방문하든 2, 1 순서로 방문하든 해당 경로를 이용하는 것은 같으므로 경로를 이용하는 두 가지 경우 모두 set에 넣어준다) set 자료구조의 특성상 추후 동일한 경로를 지나친다면 중복된 경로는 set에 저장되지 않는다.

마지막으로 경로의 순서가 다른 두 가지의 경우를 모두 set에 삽입했으므로 전체 길이를 2로 나누어 방문 길이를 구해준다.

 

 

다른 풀이 방법

def solution(dirs):
    walk_list = []
    start_location = [0,0]
    now_location = [0,0]
    for c in dirs:
        if c == 'U' and start_location[1] < 5:
            now_location = [start_location[0],start_location[1] + 1]

        elif c == 'L' and start_location[0] > -5:
            now_location = [start_location[0] - 1, start_location[1]]

        elif c == 'R' and start_location[0] < 5:
            now_location = [start_location[0] + 1, start_location[1]]

        elif c == 'D'and start_location[1] > -5:
            now_location = [start_location[0], start_location[1] - 1]

        if ([start_location,now_location] not in walk_list) and ([now_location,start_location] not in walk_list) \
                and (now_location != start_location) :
            walk_list.append([start_location,now_location])

        start_location = now_location

    return len(walk_list)