백준 14503 로봇청소기 파이썬

마이노·2022년 6월 28일
0

백준 알고리즘

목록 보기
8/10

https://www.acmicpc.net/problem/14503

풀이방법

문제를 풀면서 방향을 어떻게 해야할 지 시간을 많이 소요했었던 문제였다.

요점만 살펴보자면

1.현재 위치를 청소
2.현재 위치에서 다음을 반복하면서 인접한 칸을 탐색
3.현재 위치의 왼쪽칸이 청소가 안되어있으면, 왼쪽 방향으로 회전 ->
한 칸을 전진 ->해당칸 청소
청소가 되어있으면 왼쪽 방향으로 회전
4.해당칸 청소를 하지않거나 후진하지 않고 3번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

말로적으면서도 나는 이해가 되지 않는다.

n,m = map(int,input().split())
r,c,d = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,1,0,-1]

간단하게 입력정보를 받고
dx,dy를 살펴보자. 해당문제에는 방향이 정해져있다. 왼쪽방향으로 돈다는
정보가 있으므로 순서를 정해주어야 한다.
dx[0],dy[0]은 -1과 0 이므로 북쪽을 나타내며
순서대로 총 북,동,남,서를 나타낸다.
왼쪽으로 돈다는 말은 북 -> 서 -> 남 -> 동 -> 북 ... 이런식이 될 것이다.

따라서 해당 식을 넣을 것인데

d = (d-1) % 4

초기의 방향은 북으로 정해져있다. 이는 0이므로 위에서 말한
dx[0],dy[0]은 북이라는 말이다.
해당 수식 d에 0을 대입하게 되면 3이 나온다. 서쪽의 방향이라는 말이다.
다음 반복문을 돌면서 d의 값에 -1을 하면서 왼쪽으로 돌게끔 만들었다.

이런 사소한것에서 한시간넘게 소요해버렸다....ㅠ 사소하지만 문제를 푸는 키포인트..!!

코드

n, m = map(int, input().split())
r, c, d = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 북동남서
x, y = r, c  # 현재의 청소기 위치를 x,y에 저장한다.
graph[x][y] = 2  # 청소했다는 의미의 2를 저장한다.
# 해당문제에서 0은 빈공간,1은 벽을 의미하기에
# 2라는 숫자로 설정해둔 것 뿐이다

clean_cnt = 1  # 초기 로봇청소기위 위치를 청소했으니
# 청소의 의미로 카운트를 1로 초깃값을 잡는다.

while True:
    check = False
    for _ in range(4):
        d = (d - 1) % 4
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < m:  # 청소기의 위치가 맵을 벗어나지 않으면서
            if graph[nx][ny] == 0:  # 청소를 아직 안했다면
                graph[nx][ny] = 2  # 청소를 해주고
                clean_cnt += 1
                # 청소카운트를 더해주고
                x, y = nx, ny  # 현재위치를 x,y에 넣어준다
                check = True  # 청소를 했으니 True로 바꾼다
                break
    if not check:  # 4방향을 돌았는데 청소를 못했으면 후진준비
        nx = x - dx[d]
        ny = y - dy[d]
        if 0 <= nx < n and 0 <= ny < m:  # 후진 할수 있으면서
            if graph[nx][ny] == 2:  # 청소를 했다면
                x, y = nx, ny  # 후진
            elif graph[nx][ny] == 1:  # 벽이라면
                print(clean_cnt)  # 출력하고 종료
                break
        else:  # 후진도 못하면
            print(clean_cnt)  # 청소카운트를 출력하고 종료
            break

정말 많이배운문제다. 호되게 당함ㅠ

profile
아요쓰 정벅하기🐥

0개의 댓글