Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 백준 15685
- 프로래머스
- 백준 17626
- java
- Spring
- 백준
- 웹어플리케이션 서버
- JVM
- Coroutine
- 백준 19238
- MSA
- 백준 16719
- springboot
- 프로그래머스
- spring security
- 백준 16236
- 파이썬
- Spring Boot
- spring oauth
- spring cloud
- Kotlin
- 백준 17779
- JPA
- 백준 16235
- 백준 파이썬
- java 기술면접
- with recursive
- sql 기술면접
- re.split
- MySQL
Archives
- Today
- Total
시작이 반
[백준] 14503번(python 파이썬) 본문
SMALL
2차원 리스트에서 로봇 청소기가 청소하는 구역을 구하는 문제
구현, 시뮬레이션 문제인데 맵 이동 문제는 보통 DFS, BFS로 푸는데 어떻게 풀어야 할지 몰라서 일단 생각나는데로 풀었다. 내일 DFS로도 풀어본다.
리스트 탐색문제는 dx, dy로 보통 푸는것 같다.
풀이
시작 위치를 방문(청소)을 했다고 지정해준후 함수를 시작시킨다.
무한루프를 사용
- 현재 방향의 왼쪽의 좌표를 구한다
- 구한 좌표가 방문(청소)를 하지 않고 벽이 아닐경우
- 현재 좌표를 구한 좌표로 바꿔준다. 방향도 현재방향의 왼쪽으로 바꿔주고 (ex. 현재 방향이 북(0)이면 서(3))
방문(청소)처리하고 카운트 증가.
- 벽이거나, 방문(청소)한곳이면
- 방향만 바꿈, 턴 횟수 증가
- 턴 횟수가 4일때 후진, 후진할수 없을경우 반복문 종료
row, col = map(int, input().split())
x, y, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(row)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1] # 북 동 남 서
visited = [[False] * col for _ in range(row)]
def robot(x, y, d, visited):
clean_count = 1
turn_count = 0
while True:
next_x = x + dx[(d - 1) % 4]
next_y = y + dy[(d - 1) % 4]
if not visited[next_x][next_y] and graph[next_x][next_y] == 0: # 청소x, 벽x
x, y = next_x, next_y
d = (d - 1) % 4 # 방향 바꿈
visited[x][y] = True # 청소
clean_count += 1
turn_count = 0
continue
elif visited[next_x][next_y] or graph[next_x][next_y] == 1: # 벽o, 청소o 방향만 바꿈
d = (d - 1) % 4
turn_count += 1
if turn_count == 4: #후진
next_x = x + dx[(d + 2) % 4]
next_y = y + dy[(d + 2) % 4]
if graph[next_x][next_y] == 0:
x = next_x
y = next_y
turn_count = 0
else:
break
return clean_count
visited[x][y] = True
print(robot(x, y, d, visited))
LIST
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 2206번(python 파이썬) (0) | 2021.01.08 |
---|---|
[백준] 1697번(python 파이썬) (0) | 2021.01.08 |
[백준] 7569번(python 파이썬) (0) | 2021.01.07 |
[백준] 7576번(python 파이썬) (0) | 2021.01.07 |
[백준] 2178번(python 파이썬) (0) | 2021.01.06 |