[백준] 14503 청소기

문제 설명

• 조건이 많은 구현문제
• bfs 사용하여 해결할 수 있다.
• 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다.
  • 여기서 방향은 다음과 같음을 유추할 수 있다.
  • 또한 현재 방향에 따라 왼쪽이 달라지게 되는데 현재 북(0)쪽을 보고 있다면 왼쪽은 서쪽(3)이 된다. 이를 응용하기 위해 dr, dc 배열과 modular 연산을 이용한다.

    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    현재 방향이 1이라면 -> 배열의 0 번째 값들을 사용해 북쪽으로 이동시킬 준비를 한다.
    (현재 방향 + 3) % 4 = 왼쪽회전 방향

• 큐는 사용하지 않고 문제의 조건대로 현재 방향을 기준으로 왼쪽으로 회전하며 갈 수 있는지를 확인하고 갈 수 없다면 바뀐 방향의 왼쪽으로 돌고 같은 자리에서 4방향을 모두 검사했다면 후진해야 한다.
  • 전진 할 때 현재 r 좌표와 c 좌표에 이동방향을 더해줬다면 후진할 때는 이동방향을 빼주면 된다.

코드

n, m = map(int, input().split())
r, c, d = map(int, input().split())
graphs = []

for _ in range(n):
    graphs.append(list(map(int, input().split())))

visited = [[False] * m for _ in range(n)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

visited[r][c] = True
cnt = 1

while True:
    flag = True
    for _ in range(4):
        d = (d + 3) % 4
        nr = r + dr[d]
        nc = c + dc[d]
        if 0 <= nr < n and 0 <= nc < m and graphs[nr][nc] == 0 and not visited[nr][nc]:
            visited[nr][nc] = True
            cnt += 1
            r = nr
            c = nc
            flag = False
            break
    if flag:
        if graphs[r - dr[d]][c - dc[d]] == 1:
            print(cnt)
            break
        else:
            r, c = r - dr[d], c - dc[d]

• flag 변수 명을 back 같은 단어로 바꾸면 좀 더 직관적이였을듯
• 회전한다와 후진한다에서 당황했는데 생각보다 깔끔한 문제라서 좋았음
• 큐를 안쓰고 해결하는 bfs는 처음이였는데 while 문 탈출조건과 다음 이동 순서가 명확하게 있어서 이렇게도 bfs 해결이 가능하다는 것을 알았음