s5unnyjjj's LOG
[홀로 하는 코딩 공부] 리코쳇 로봇(Python) 본문
프로그래머스
사용 언어: Python
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
*** 본 문제를 푸는 과정을 공유하려 한다.
▶ 처음 문제를 보고 DFS 구현을 떠올려서 DFS 알고리즘을 아래와 같이 구현하였다.
direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def moving(pos, di, board):
lenY, lenX = len(board), len(board[0])
cx, cy = pos[0], pos[1]
nx, ny = pos[0], pos[1]
if di[0] == 0:
for i in range(1, lenX):
ndi = di[1] * i
if 0 <= cy + ndi < lenX:
if board[cx][cy + ndi] == 'D':
nx, ny = cx, cy + di[1] * (i - 1)
break
if cy + ndi == (lenX - 1):
nx, ny = cx, lenX - 1
break
if cy + ndi == 0:
nx, ny = cx, 0
break
else:
break
elif di[1] == 0:
for i in range(1, lenY):
ndi = di[0] * i
if 0 <= cx + ndi < lenY:
if board[cx + ndi][cy] == 'D':
nx, ny = cx + di[0] * (i - 1), cy
break
if cx + ndi == (lenY - 1):
nx, ny = lenY - 1, cy
break
if cx + ndi == 0:
nx, ny = 0, cy
break
else:
break
return nx, ny
def dfs(cur_pos, end_pos, board, visited, cnt, best_cnt):
if cur_pos == end_pos:
best_cnt.add(cnt)
return best_cnt
for di in direct:
nx, ny = moving(cur_pos, di, board)
if cur_pos == [nx, ny]:
continue
if visited[nx][ny] == 1:
best_cnt.add(-1)
else:
visited[nx][ny] = 1
best_cnt = dfs([nx, ny], end_pos, board, visited, cnt + 1, best_cnt)
visited[nx][ny] = 0
return best_cnt
def solution(board):
start_pos, end_pos = [], []
lenY, lenX = len(board), len(board[0])
visited = [[0 for _ in range(lenX)] for _ in range(lenY)]
for i in range(lenY):
for j in range(lenX):
if board[i][j] == 'R':
start_pos = [i, j]
visited[i][j] = 1
elif board[i][j] == 'G':
end_pos = [i, j]
if start_pos and end_pos:
break
answer = dfs(start_pos, end_pos, board, visited, 0, set())
return list(answer)[0]
from collections import deque
direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def moving(pos, di, board):
lenY, lenX = len(board), len(board[0])
cx, cy = pos[0], pos[1]
nx, ny = pos[0], pos[1]
if di[0] == 0:
for i in range(1, lenX):
ndi = di[1] * i
if 0 <= cy + ndi < lenX:
if board[cx][cy + ndi] == 'D':
nx, ny = cx, cy + di[1] * (i - 1)
break
if cy + ndi == (lenX - 1):
nx, ny = cx, lenX - 1
break
if cy + ndi == 0:
nx, ny = cx, 0
break
else:
break
elif di[1] == 0:
for i in range(1, lenY):
ndi = di[0] * i
if 0 <= cx + ndi < lenY:
if board[cx + ndi][cy] == 'D':
nx, ny = cx + di[0] * (i - 1), cy
break
if cx + ndi == (lenY - 1):
nx, ny = lenY - 1, cy
break
if cx + ndi == 0:
nx, ny = 0, cy
break
else:
break
return nx, ny
def bfs(cur_pos, end_pos, board, visited):
que = deque()
que.append(cur_pos)
visited[cur_pos[0]][cur_pos[1]] = 0
while que:
cx, cy = que.popleft()
for di in direct:
nx, ny = moving([cx, cy], di, board)
if [nx, ny] == end_pos:
return visited[cx][cy] + 1
elif visited[cx][cy] + 1 < visited[nx][ny]:
que.append([nx, ny])
visited[nx][ny] = visited[cx][cy] + 1
return -1
def solution(board):
start_pos, end_pos = [], []
lenY, lenX = len(board), len(board[0])
visited = [[float('inf') for _ in range(lenX)] for _ in range(lenY)]
for i in range(lenY):
for j in range(lenX):
if board[i][j] == 'R':
start_pos = [i, j]
visited[i][j] = 1
elif board[i][j] == 'G':
end_pos = [i, j]
if start_pos and end_pos:
break
ans = bfs(start_pos, end_pos, board, visited)
return ans
▶ 두 가지의 테스트 케이스는 그냥 통과했지만, 제출하니 두 가지를 제외한 모든 테스트 케이스에서 시간초과가 났다.(심지어 자세히보면 11번은 틀렸다) 틀린부분을 해결해도 시간초과가 문제이니, BFS 구현으로 방향을 틀었다.
from collections import deque
direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def moving(pos, di, board):
lenY, lenX = len(board), len(board[0])
cx, cy = pos[0], pos[1]
nx, ny = pos[0], pos[1]
if di[0] == 0:
for i in range(1, lenX):
ndi = di[1] * i
if 0 <= cy + ndi < lenX:
if board[cx][cy + ndi] == 'D':
nx, ny = cx, cy + di[1] * (i - 1)
break
if cy + ndi == (lenX - 1):
nx, ny = cx, lenX - 1
break
if cy + ndi == 0:
nx, ny = cx, 0
break
else:
break
elif di[1] == 0:
for i in range(1, lenY):
ndi = di[0] * i
if 0 <= cx + ndi < lenY:
if board[cx + ndi][cy] == 'D':
nx, ny = cx + di[0] * (i - 1), cy
break
if cx + ndi == (lenY - 1):
nx, ny = lenY - 1, cy
break
if cx + ndi == 0:
nx, ny = 0, cy
break
else:
break
return nx, ny
def bfs(cur_pos, end_pos, board, visited):
que = deque()
que.append(cur_pos)
visited[cur_pos[0]][cur_pos[1]] = 0
while que:
cx, cy = que.popleft()
for di in direct:
nx, ny = moving([cx, cy], di, board)
if [nx, ny] == end_pos:
return visited[cx][cy] + 1
elif visited[cx][cy] + 1 < visited[nx][ny]:
que.append([nx, ny])
visited[nx][ny] = visited[cx][cy] + 1
return -1
def solution(board):
start_pos, end_pos = [], []
lenY, lenX = len(board), len(board[0])
visited = [[float('inf') for _ in range(lenX)] for _ in range(lenY)]
for i in range(lenY):
for j in range(lenX):
if board[i][j] == 'R':
start_pos = [i, j]
visited[i][j] = 1
elif board[i][j] == 'G':
end_pos = [i, j]
if start_pos and end_pos:
break
ans = bfs(start_pos, end_pos, board, visited)
return ans
▶ 평소에 DFS보다 BFS 구현에 더 자신있어서 항상 이런문제를 보면 BFS를 이용하여 풀었었다. 그런데 이번문제는 스스로 DFS에도 자신감을 갖고자 DFS로 시작하였다. 하지만 board길이가 100까지인 것을 봤으면 BFS로 시작을 했어야했는데, 문제를 꼼꼼히 보지 못한 것 같다.
>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.
>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.
>> 긴 글 읽어주셔서 감사합니다.
반응형
'Algorithm > Python' 카테고리의 다른 글
| [홀로 하는 코딩 공부] 이모티콘 할인행사(Python) (2) | 2024.05.01 |
|---|---|
| [홀로 하는 코딩 공부] 혼자서 하는 틱택토(Python) (0) | 2024.04.22 |
| [홀로 하는 코딩 공부] 광물 캐기(Python) (0) | 2024.04.16 |
| [홀로 하는 코딩 공부] 연속된 부분 수열의 합(Python) (0) | 2024.04.15 |
| [홀로 하는 코딩 공부] 토마토 (Python) (4) | 2024.04.06 |
'Algorithm/Python' Related Articles
more
Comments