[백준] 14503번(python 파이썬)

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

 

---

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))