[백준] 14503_로봇 청소기

📕 문제

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

14503번: 로봇 청소기

 

💡 풀이법

: 처음에 그래프를 보고 바로 dfs겠거니 해서 dfs로 풀다가 dfs가 아닌 단순 구현임을 알았다.

하지만 코드가 dfs랑 비슷하다.. 이런것도 dfs라 그러나?..ㅋㅋ

 

1. area가 존재하면 계속 while문을 실행한다.

2. while문이 실행되면 x, y, d를 할당해주고 area를 0으로 바꾼다.

3. 먼저 현재 보는 방향에 따라 탐색 순서가 다르다.

북쪽(0) : 서 -> 남 -> 동 -> 북

동쪽(1) : 북 -> 서 -> 남 -> 동

남쪽(2) : 동 -> 북 -> 서 -> 남

서쪽(3) : 남 -> 동 -> 북 -> 서

루틴은 같은데 시작점이 다르다. 그래서 방향에 따라 사방을 탐색할때 시작 위치를 달리 해줬다.

 

4. 사방을 탐색하며 갈수 있다면 area를 갈수 있는 위치로 변화시켜준다.

(이때, 방향도 현재 방향이 d라면 (d+3)%4로 바뀜)

그리고 for문을 break 해준다.

5. 만약 사방을 다 탐색했는데도 청소 할 수 있는 장소가 없거나 벽이라면, 뒤로 후진하는데 갈수 있는 곳이라면 area를 후진한 위치로 변화시켜준다.

6. 만약 위의 2, 3 모두 안된다면, area가 그대로 0이기 때문에 while문이 더이상 실행되지 않는다.

(작동이 멈춘다)

 

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
def clean(r, c, d):
    area = (r, c, d)
    visited[r][c] = 1

    while area:
        x, y, d = area
        area = 0

        if d % 2:
            temp = (d + 2) % 4
        else:
            temp = d

        for i in range(4):
            nx, ny = x + dx[(temp + i) % 4], y + dy[(temp + i) % 4]
            d = (d + 3) % 4

            if -1 < nx < N and -1 < ny < M and not visited[nx][ny] and not matrix[nx][ny]:
                visited[nx][ny] = 1
                area = (nx, ny, d)
                break
        else:
            if d % 2:
                idx = d - 1
            else:
                idx = d + 1
            nx, ny = x + dx[idx], y + dy[idx]
            if -1 < nx < N and -1 < ny < M and not matrix[nx][ny]:
                area = (nx, ny, d)


N, M = map(int, input().split())
r, c, d = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
clean(r, c, d)
ans = 0
for i in range(N):
    ans += sum(visited[i])
print(ans)