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
- 코테
- wordcloud
- 알고리즘
- 시각화
- 백준
- 추천 시스템
- coursera
- TF-IDF
- SGD
- 프로그래머스
- 데이터
- selenium
- Tensor
- 딥러닝
- Cosine-similarity
- 웹스크래핑
- Python
- 데이터 엔지니어링
- codingtest
- recommendation system
- 부스트캠프
- 분산 시스템
- Overfitting
- 코딩테스트
- 협업 필터링
- 추천시스템
- pytorch
- 웹크롤링
- 머신러닝
- 파이썬
Archives
- Today
- Total
개발자식
[백준] Python, 시뮬레이션 14503 본문
✔︎ 문제:
https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽
www.acmicpc.net
✏️ 나의 풀이
- 이 문제는 직접 그려서 이동했을 때, 예제와 같은 값이 나오지 않아 문제를 여러번 읽었었다..! 일단 1번으로 돌아간다는 말은 전체 1번을 의미한다.
- 문제 그대로를 구현하면 되는데,
1. 현재 칸의 청소 유무와 벽인지 아닌지 구분이 필요하고
2. 주변이 청소되어 있는지 확인한다.
3. 주변이 모두 청소가 되어있다면 후진해서 다시 1, 2를 확인한다.
- 시계 반대 방향과 후진 방향의 이동을 딕셔너리를 이용해서 직관적으로 박아뒀다. (무식하지만..ㅎㅎ)
- 기존 배열은 벽인지 구분하는 용도로 활용하고, 청소한 곳은 visitied 배열로 확인한다.
- 재귀함수로 이동할 수 있는 모든 경우를 탐색한후, 후진 했을 때 주변에 이동할 수 있는 곳이 없고 벽에 도달한다면 탐색을 종료한다.
def check(r,c,d):
global count
for i in move[d]:
dx, dy = direction[i][0], direction[i][1]
nx, ny = dx+r, dy+c
if arr[nx][ny] == 0 and not visited[nx][ny]:
visited[nx][ny] = True
count += 1
if not check(nx,ny,i):
return False
bx, by = direction[back[d]][0]+r, direction[back[d]][1]+c
if arr[bx][by] == 0: #후진
check(bx, by, d)
else:
return False
direction = {0:(-1,0), 1:(0,1), 2:(1,0),3:(0,-1)} #북, 동, 남, 서
move = {0:[3,2,1,0], 1:[0,3,2,1], 2:[1,0,3,2], 3:[2,1,0,3]}
back = {0:2, 2:0, 3:1, 1:3}
n,m = map(int, input().split())
r,c,d = map(int, input().split())
arr = []
visited = [[False] * m for i in range(n)]
for i in range(n):
arr.append(list(map(int, input().split())))
count = 0
count +=1
visited[r][c] = True
while True:
if not check(r,c,d):
break
print(count)
🔎다른 풀이
- 반복문으로 이동했고, 이동하는 방향을 [현재 방향 +3 % 4]로 설정할 수 있다.
import sys
input = sys.stdin.readline
from collections import deque
n,m = map(int,input().split())
graph = []
visited = [[0] * m for _ in range(n)]
r,c,d = map(int,input().split())
dx = [-1,0,1,0]
dy = [0,1,0,-1]
for _ in range(n):
graph.append(list(map(int,input().split())))
visited[r][c] = 1
cnt = 1
while 1:
flag = 0
for _ in range(4):
nx = r + dx[(d+3)%4]
ny = c + dy[(d+3)%4]
d = (d+3)%4
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
if visited[nx][ny] == 0:
visited[nx][ny] = 1
cnt += 1
r = nx
c = ny
flag = 1
break
if flag == 0:
if graph[r-dx[d]][c-dy[d]] == 1:
print(cnt)
break
else:
r,c = r-dx[d],c-dy[d]
'Algorithm > Baekjoon' 카테고리의 다른 글
[백준] 19799_ 자료구조 (1) | 2023.05.24 |
---|---|
[백준] 1439_ 그리디, 문자열 (0) | 2023.05.24 |
[백준] DP_2579 python (0) | 2022.11.10 |
[백준] DP_1003, 9461, 11726, 11727, 9095, 1463, 2193, 11053_python (2) | 2022.09.11 |
[백준] 재귀함수, 정렬_ 2447, 2750, 10989, 10814, 1427, 2947, 1431, 18870 (0) | 2022.09.07 |
Comments