빛의 경로 사이클

문제

처음 짠 코드

from curses.ascii import isalnum


def solution(grid):
    answer = []

    lenRow = 2*len(grid) + 1
    lenCol = 2*len(grid[0]) + 1
    # print(lenRow) # 5
    # print(lenCol) # 5

    totalMap = [[0] * lenCol for _ in range(lenRow)]
    # print(totalMap)

    # grid = ["SL","LR"]
    i = 0
    j = 0

    for row in range(lenRow):
        if row % 2 != 1:
            continue
        # print("row = ", row)
        for col in range(lenCol):
            if col % 2 != 1:
                continue
            # print("col = ", col)
            totalMap[row][col] = grid[i][j]
            # print("i = ", i, " j = ", j)
            if j == len(grid[0])-1:
                i += 1
                j = 0
            else:
                j += 1
            
            if i == len(grid):
                break
        if i == len(grid):
            break

    # print(totalMap)
            

    def dfs(M, row, col, D, lenRow, lenCol):
        input()
        if row == 1 and col == 1:
            # 다시 출발점으로 돌아왔으면
            return M

        if str(M[row][col]).isalpha():
            print("여기는 노드", M[row][col])
            if M[row][col] =="U":
                dfs(M, row+1, col, "U", lenRow, lenCol)

            if M[row][col] =="L":
                dfs(M, row, col-1, "L", lenRow, lenCol)

            if M[row][col]=="D":
                dfs(M, row-1, col, "D", lenRow, lenCol)

            if M[row][col]=="R":
                dfs(M, row, col+1, "R", lenRow, lenCol)

        # 방문한 곳 1로 체크
        M[row][col] = 1
        print("( ", row,",", col, " )")
        
        # 다음 갈 곳이 범위 넘어가는 곳이면 자리 이동
        
        if D =="U":
            if row == 0:
                dfs(M, lenRow-1, col, D, lenRow, lenCol)
            else:
                dfs(M, row-1, col, D, lenRow, lenCol)

        if D =="L":
            if col == 0:
                dfs(M, row, lenCol-1, D, lenRow, lenCol)
            else:
                dfs(M, row, col-1, D, lenRow, lenCol)

        if D=="D":
            if row == lenRow-1:
                dfs(M, 0, col, D, lenRow, lenCol)
            else:
                dfs(M, row+1, col, D, lenRow, lenCol)


        if D=="R":
            if col == lenCol-1:
                dfs(M, row, 0, D, lenRow, lenCol)
            else:
                dfs(M, row, col+1, D, lenRow, lenCol)

    row = 1
    col = 1
    # print(lenRow)

    print("UP 시작")
    mapUp = dfs(totalMap, row-1, col, "U", lenRow, lenCol)
    print("Right 시작")
    mapRight = dfs(totalMap, row, col+1, "R", lenRow, lenCol)
    mapDown = dfs(totalMap, row+1, col, "D", lenRow, lenCol)
    mapLeft = dfs(totalMap, row, col-1, "L", lenRow, lenCol)




    return answer

grid = ["SL","LR"]
# results = [16]

# grid = ["S"]
# results = [1,1,1,1]

# grid = ["R","R"]	
# results = [4,4]

print(solution(grid))

1시간 넘게 머리 굴렸는데 결국 못풀었다. 해설을 찾아보니 문제의 출제 의도는 "4방향 이동 및 회전을 구현할 수 있는지" 였다.

정확하게 그걸 할 줄 모른다. 백준 문제 중에 로봇청소기? 문제랑 비슷한 것 같다. 어거지로 풀었던 기억이 있는데(아마 그 때도 못풀고 답지를 봤었던 것 같다)

처음 내가 접근했던 방식과 흐름은 유사한데(특별한 알고리즘이 필요한 건 아니었고 구현/시뮬레이션 문제였다) 정답 코드는 코드가 좀 더 간결하고 가장 중요한 4방향 회전이 핵심이었다.

정답 코드 (프로그래머스 해설 참고)

def move(r, c, d):
    global directions, n, m
    dx, dy = directions[d]
    return (r + dx) % n , (c + dy) % m

def rotate(d, node):
    if node == 'R':
        d = (d + 1) % 4
    elif node == 'L':
        d = (d - 1) % 4
        # -1 % 4 => 3
    return d

def solution(grid):
    # grid = ["SL","LR"]

    global n, m, answer, directions
    answer = []
    n = len(grid) # 2 , row
    m = len(grid[0]) # 2, col

    visited = [[[False for _ in range(4)] for _ in range(m)] for _ in range(n)]
    # print("visited = ", visited)
    # 모든 방향이 False인 길이 4짜리 1차원 배열 -> 이게 원소 한 개, => 이게 m(col) x n(row) 사이즈로
    directions = [[1, 0], [0, -1], [-1, 0], [0, 1]] 
    # D, L, U, R

    for r in range(n):
        for c in range(m):
            for d in range(4):
                # 아래, 왼쪽, 위, 오른쪽 전부 본다
                input()
                print("r, c, d = ", r,c,d)
                if not visited[r][c][d]:
                    cx, cy, cd = r, c, d
                    cnt = 0
                    while not visited[cx][cy][cd]:
                        # True 가 나오면 while 나와
                        visited[cx][cy][cd] = True
                        cnt += 1
                        cx, cy = move(cx, cy, cd)
                        # 다음 번 방문할 곳
                        cd = rotate(cd, grid[cx][cy])
                        # 다음 번 방문할 곳에서 방향
                    answer.append(cnt)
    return sorted(answer)

grid = ["SL","LR"]
# results = [16]

# grid = ["S"]
# results = [1,1,1,1]

# grid = ["R","R"]	
# results = [4,4]

print(solution(grid))

핵심

visited = [[[False for _ in range(4)] for _ in range(m)] for _ in range(n)]
# print("visited = ", visited)

모든 방향이 False인 길이 4짜리 1차원 배열 -> 이게 원소 한 개
=> 이게 m(col) x n(row) 사이즈로 Map 구성

directions = [[1, 0], [0, -1], [-1, 0], [0, 1]] 
# D, L, U, R

4가지 방향 배열

if not visited[r][c][d]:

그 칸에서 -> (r, c) 자리에서 그 방향으로 안했으면 진행, 이미 한번 했으면 안해 -> 어차피 똑같은 결과니까 -> 같은 사이클

def move(r, c, d):
  global directions, n, m
  dx, dy = directions[d]
  return (r + dx) % n , (c + dy) % m

+dx, +dy 는 그 방향으로 전진, %n, %m 은 한칸 가보니까 넘친다 => 다시 0으로 돌아가

def rotate(d, node):
  if node == 'R':
      d = (d + 1) % 4
  elif node == 'L':
      d = (d - 1) % 4        
  return d

방향 회전 코드 -> 외워두자
아래 방향으로(cd가 0: "D") 온 경우, 온 자리가 L 이면? (내가 화면을)정면으로 봤을 때 오른쪽으로 틀어야 한다. 그럼 return 값(cd)는 3(R)이 되어야 한다.
( -1 % 4 => 3 , 1 % 4 => 1 임에 주의 )

return sorted(answer)

문제의 끝부분 구석탱이에 정답을 정렬해서 내라고 나와있다.