< 프로그래머스 / 월간 코드 챌린지 > 빛의 경로 사이클

https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

요즘 프로그래머스 2단계를 학살하는 재미에 빠져있는데, 그 과정에서 만난 짐승같은 문제...

요즘 팀플이다 과제다 뭐다 매우 바빠서, 공부 사이사이에 짬을 투자해서 한문제씩 풀어나가는 재미에 빠졌는데

이 문제는 어제 만나서 오늘 풀게 되었다.

사실 문제를 이해하고 풀이를 떠올리고 구현하는데는 20분 내에 충분히 했던 것 같다. 

다만, 모래 위에 지은 모래성 실력때문인지 항상 while 문을 사용할 때, 입 출력의 순서, 안에서 체크해야 하는 조건 및 조건의 작동 순서 를 

고민하는게 항상 느리고 힘들었는데, 이 문제에서 터져버렸던 것 같다. 

그래서 구현 다하고 마지막에 while 문 쓰다가 코딩을 잠시 멈추고 오늘 다시 풀어 본 것이다. 

 

빛의 경로 사이클 문제

처음에 문제를 보고 당황했다. 격자구조는 머고 이건 뭔지. 문제 이해하는데 시간이 걸리고, 문제에서 표현한 방식을 내가 다룰 수 있는 표현으로 어떻게 가공할 지를 생각하는데 시간이 걸렸다.

결국 보이는 모습만 무서웠지만, 결국 이차원 배열로 충분히 표현이 가능한 문제였다.

또한 요즘은 딕셔너리를 자주 쓰려고 하는데, 최근 효율성을 테스트하는 다른 문제를 통해 시간 복잡도에 대한 고민을 하게 된 것 같다. 

모든 문제에서 시간 복잡도를 고려 하진 않지만, 적어도 N 의 최대 개수는 몇개인지

파이썬 기준 1초, 2천만번 연산 안에 해결할 수 있는지 등등 말이다. 

무튼, x in y  방식의 코드를 그 동안은 너무 편해서 자주 사용했지만 O(n)의 시간 복잡도를 지닌다는 것을 알게되고

더 적은 탐색시간을 가지는 코드가 없을 까 하다가 발견하게된 dict.get(찾을 대상, 찾을 대상이 없다면 리턴할 값) 을 알게 되어 이것을 사용하려고 노력하고 있다. 시간 복잡도는 O(1) 이다. dict 에서도 역시 x in y 의 형태는 O(n) 이다.

 

아무튼 풀이에 대해 이야기 하면, 저 복잡한 그림을 어떻게 배열로 표현 할 지를 고민해야 하는데  위에 보이는 저 화살표들이 사실 출발한 문자 안에 들어가 있다고 생각하면 편하다. 

'S' 의 경우에는 <-- (13),  -->(5), 아래화살표(1), 위 화살표(9) 를 지니고 있는 것이다 .

또한 빛의 사이클의 특성 상 숫자는 중요하지 않다.  가령 위 그림에서 'S' 위치에 첫번째로 <-- 화살표가 왔다고 하더라도 결국 사이클은 순환하고 똑같은 모습과 개수를 지니기 때문이다. 

따라서 우리는 저 'S'의 위치에 상, 하, 좌, 우 라는 빛의 방향을 저장 해야 하고,

만약 상, 하, 좌 만 있다면     '우' 오른방향 빛을 쏘게 되면 다른 사이클이 만들어 지게 되는 것이다. 

그래서 이중리스트에 빛의 4방향 탐색이 이루어지게 되는 것이다. 

 

def solution(grid):  # 500 * 500 총 25000 개 그리드에 , 4방향탐색이면 최대 10만회의 탐색
    answer = []
    # 상0 오른1 하2 왼3 ->시계방향
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    save = [[{} for __ in _] for _ in grid]  # 방향을 저장할 공간 -> 이거 움직인 방향 그냥 저장해도 됨:: 그래야 완전탐색이 가능해짐.
    board = [[g for g in _] for _ in grid]
    # 빛의 움직임을 구현 해봅시다.

    max_r, max_c = len(grid) - 1, len(grid[0]) - 1
    for i in range(4):
        for ir, r in enumerate(save):
            for ic, c in enumerate(r):  # c: dict 방향저장용 True, False 로 저장
                if c.get(i, False):
                    continue  # 다음 블록으로 이동해서 탐색
                #처음 만나는 블록일 때
                count = 1# 현재 방향 위치에 저장하구 r, c 위치를 변화시켜서 while 문에 넘기면 됨
                c[i] = True
                ir, ic = ir + move[i][0], ic + move[i][1]
                if ir > max_r:
                    ir = 0
                elif ir < 0:
                    ir = max_r

                if ic > max_c:  # 벽을 만날때 튀어나오는 케이스 테스트하기
                    ic = 0
                elif ic < 0:
                    ic = max_c

                while True:
                    if board[ir][ic] == 'R':
                        i += 1
                    elif board[ir][ic] == 'L':
                        i -= 1

                    if i < 0:  # i 조정시키기
                        i = 3
                    elif i > 3:
                        i = 0

                    if save[ir][ic].get(i, False): #
                        break  # 같은 방향이 있다는것(사이클이 돌았다는 뜻) 반복문 종료
                    count += 1 # 한 번 이동 체크
                    save[ir][ic][i] = True #### 화살표 방향 저장 --> 종료조건
                    ir, ic = ir + move[i][0], ic + move[i][1] # 이동할 위치 저장
                    if ir > max_r:
                        ir = 0
                    elif ir < 0:
                        ir = max_r

                    if ic > max_c:  #벽을 만날때 튀어나오는 케이스 테스트하기
                        ic = 0
                    elif ic < 0:
                        ic = max_c

                answer.append(count)

    # answer.sort(reverse=True) #--> 요건 내림차순을 이야기 하는 코드
    answer.sort()
    return answer

문제를 깔끔 하게 풀었다고 생각해서 채점을 했는데 테스트 케이스에서 하나 맞고 다틀려서 100점 만점에 8점이 나왔었다. 

어이가 없어서 서칭을 하다가 문제의 조건인 오름차순으로 배열하라는 조건을 내가 잘못 해석한 것을 깨달았다. 

오름차순이란 조건을 보고 큰 수부터 나열하라는 거겠구나 했는데, 그게 아니라 작은 수부터 나열하라는 의미의 한국어 였다 ㅜㅜ

그래도 25분 서칭에 내 실수를 발견해서 싸게 먹혀서 너무 다행이다 ㅎ