🔗
풀이
보통의 그래프 탐색과 다르게 이 문제는 경로를 목적으로 한다.
일반적인 그래프 탐색 문제는 (0, 0)과 같은 특정 위치에서 다른 위치로 옮겨다녔지만 이 문제는 (0, 0)에서 (1, 1)으로 갔다는 경로와 방향성이 중요한 것이다. 위치를 탐색하는 걸 경로를 탐색하는 걸로 바꾸면 일반 그래프 탐색 문제와 크게 다를 게 없다. 방문처리도 위치가 아니라 경로로 해주면 된다.
단, 경로가 그래프의 크기를 벗어나게 되면 한 바퀴 돌아서 반대쪽 행이나 열로 다시 돌아온다는 점에 유의하면 된다
우선 (0, 0)에서 시작해서 아래 방향부터 4방향의 경로를 파악한 후에 탐색할 수 있는 경로라면 들어가서 재귀로 탐색을 시작한다. d 방향으로 이동하고 위치를 찾으면 그 위치의 값에 따라 방향을 바꾸고 다시 d 방향으로 이동을 반복한다. 그러다 이미 방문한 경로를 찾으면 탐색을 종료하고 탐색한 경로 횟수 = 재귀 함수의 개수이므로 return 값에 cycle 함수를 넣고 +1을 하면 총 재귀 함수의 개수를 구할 수 있다.
재귀를 사용했는데 grid의 최대 길이가 500이라서 파이썬 재귀 횟수로는 한계가 있어서 setrecursionlimit를 좀 더 늘려줬다. 이걸 안 해줘서 처음에 런타임 에러가 떴었다.
내 풀이
visited = {}
di, dj = (1, 0, -1, 0), (0, 1, 0, -1)
def cycle(grid, si, sj, ni, nj, d):
visited[(si, sj, ni, nj)] = True
# 다음에 방문할 위치 찾기
si, sj = ni%len(grid), nj%(len(grid[0]))
# 그 위치에 따라 방향 변경
if grid[si][sj] == 'L':
d = (d+1)%4
elif grid[si][sj] == 'R':
d = (d+3)%4
ni, nj = si+di[d], sj+dj[d]
# 이미 방문한 경로라면 모든 탐색을 종료
if visited.get((si, sj, ni, nj)):
return 1
# return 될 때마다 1씩 증가(경로의 개수 증가)
return cycle(grid, si, sj, ni, nj, d) + 1
def solution(grid):
answer = []
for i in range(len(grid)):
for j in range(len(grid[0])):
for k in range(4):
ni, nj = i+di[k], j+dj[k]
# 이미 방문한 경로라면 방문x
if visited.get((i, j, ni, nj)):
continue
answer += [cycle(grid, i, j, ni, nj, k)]
answer.sort()
return answer
import sys
sys.setrecursionlimit(1111111)
효율성 높은 풀이
결국 경로라는게 각 위치에서 갈 수 있는 4개의 방향으로 제한되어 있기 때문에 visited를 3차원으로 만들어서 경로의 방문처리를 할 수도 있는 것이다.
위의 풀이 시간효율성이 별로인 이유는
- 재귀라서
- 넘겨주는 인자가 불필요하게 많음
- visited가 딕셔너리라서
3가지가 전부 해당되는 것 같았다. 일단 넘겨주는 인자의 경우 solution 함수 안에 함수를 정의하고 풀면 grid배열을 매번 넘겨줄 필요가 없으니 해결되었다. visited의 경우도 딕셔너리에서 3차원 배열로 변경했다. 재귀는 반복문으로 바꿨다. 시간복잡도가 절반으로 줄어들었다.
di, dj = (1, 0, -1, 0), (0, 1, 0, -1)
def solution(grid):
answer = []
n, m = len(grid), len(grid[0])
visited = [[[0, 0, 0, 0] for _ in range(m)] for _ in range(n)]
def cycle(i, j, d):
res = 0
while not visited[i][j][d]:
visited[i][j][d] = 1
i, j = (i+di[d])%n, (j+dj[d])%m
if grid[i][j] == 'L':
d = (d+1)%4
elif grid[i][j] == 'R':
d = (d-1)%4
res += 1
return res
for i in range(n):
for j in range(m):
for k in range(4):
if not visited[i][j][k]:
pass
answer += [cycle(i, j, k)]
answer.sort()
return answer
후기
부캠 톡방에서 엄청 어렵다고 해서 긴장하고 풀었는데 레벨2라서 살짝 당황;
근데 그림이 너무 어렵게 보여서 처음엔 이거 풀 수 있나? 싶긴 했었다.
그런데 뭐만 하면 무작정 딕셔너리로 처리하는 습관을 좀 고쳐야 할 것 같다. 파이썬에서 딕셔너리 키값을 참고하는 시간복잡도가 O(1)이라서 매번 이걸 사용하는데 어떨 땐 배열보다 훨씬 오래 걸린다ㅠㅠ
그리고 프로그래머스 solution에서 사용되는 값 어떻게 다른 함수에서 가져다쓰나 했더니 내부에 함수를 정의하면 되는거였네..?!
복습
😎 3차원 배열 활용한 풀이
def solution(grid):
n, m = len(grid), len(grid[0])
visited = [[[False]*m for _ in range(n)] for _ in range(4)]
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 상 우 하 좌
ans = []
for k in range(4):
for x in range(n):
for y in range(m):
if visited[k][x][y]:
continue
cnt = 0
while not visited[k][x][y]:
visited[k][x][y] = True
x = (x+dx[k])%n
y = (y+dy[k])%m
if grid[x][y] == "L":
k = (k-1)%4
elif grid[x][y] == "R":
k = (k+1)%4
cnt += 1
ans.append(cnt)
ans.sort()
return anscycle 함수
visited 3차원 배열을 선언했다. 선언할 때 상하좌우 방향을 가리키는 4칸에 각각의 2차원 배열을 넣는 방식으로 했다. 이렇게하면 좀 더 빠르다고 하던데
def solution(grid):
n, m = len(grid), len(grid[0])
visited = [[[False]*m for _ in range(n)] for _ in range(4)]
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 상 우 하 좌
def cycle(k, x, y):
cnt = 0
while not visited[k][x][y]:
visited[k][x][y] = True
x = (x+dx[k])%n
y = (y+dy[k])%m
if grid[x][y] == "L":
k = (k-1)%4
elif grid[x][y] == "R":
k = (k+1)%4
cnt += 1
return cnt
ans = []
for k in range(4):
for x in range(n):
for y in range(m):
if visited[k][x][y]:
continue
ans.append(cycle(k, x, y))
ans.sort()
return ans
# print(solution(["SL","LR"])) # [16]
# print(solution(["S"])) # [1, 1, 1, 1]
print(solution(["R","R"])) # [4, 4]
