문제
이 문제는 문제에서 주어진 로직이 번거로워서 그렇지 구현자체는 bfs 를 이용하면 되는 문제이다.
bfs를 활용한 미로 문제를 풀 때 처럼 구현을 해주지만 여기서 문제의 조건에 맞게 변형을 해주어서 문제를 해결했다.
이때 처음 문제를 풀이했을 때 계속해서 오답이 나왔는데 왜 그런지 이유를 몰랐었다.
이후 찾게된 이유는 바로 주변 4칸에 빈칸이 있어서 반시계방향으로 회전한 후 전진을 해줄 때 전진할 곳이 청소가 되지 않은 빈칸인 경우를 고려해주지 않았기 때문이다.
이 부분은 문제에 직접적으로 주어져있지 않아서 간과하기 쉬운데 이 부분을 빠뜨리면 가야할 곳을 전부 방문하지 못한 채 종료되고 만다.
이 경우까지 고려해서 작성한 코드는
n, m = map(int, input().split())
start = list(map(int, input().split()))
rooms = [list(map(int, input().split())) for _ in range(n)]
from collections import deque
visited = [[0]*m for _ in range(n)]
ans = 0
x,y,d = start[0] , start[1], start[2]
q = deque()
q.append((x,y,d))
visited[x][y] = 1
#시작하는 곳이 청소가 안된 빈칸일 때
if rooms[x][y] == 0:
ans += 1
#청소된 곳은 2로 표시
rooms[x][y] = 2
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while(q):
x,y,d = q.popleft()
#주변 4칸 확인
check = False
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0<= nx <n and 0<= ny <m and rooms[nx][ny] == 0:
check =True
#주변 4칸 중 청소되지 않은 칸이 있는 경우
if check:
#반시계 방향으로 90도 회전
if d == 0:
nd = 3
else:
nd = d-1
# 앞쪽 칸으로 전진후 좌표 구하기
if nd == 0:
nx = x -1
ny = y
elif nd ==1:
nx = x
ny = y+1
elif nd == 2:
nx = x+1
ny = y
elif nd == 3:
nx = x
ny = y-1
#전진할 좌표가 청소되지 않은 빈칸인경우에 전진
if 0<= nx <n and 0<= ny < m and rooms[nx][ny]==0:
q.append((nx,ny,nd))
ans += 1
#청소된 곳은 2로 표시
rooms[nx][ny] = 2
#청소되지않은 빈칸이 주변에 있지만 현재의 반시계방향으로 전진했을 때 빈칸이 아닌 경우 현재위치에 바뀐 방향을 q에 추가해줌
else:
q.append((x,y,nd))
#주변4칸중 청소되지않은 빈칸 없을 경우
else:
#후진 시의 좌표값 구하기
if d == 0:
nx = x+1
ny = y
elif d ==1:
nx = x
ny = y-1
elif d == 2:
nx = x -1
ny = y
elif d == 3:
nx = x
ny = y+1
#후진할 곳이 벽이 아니라면
if 0<= nx <n and 0<= ny < m and rooms[nx][ny]!=1:
q.append((nx,ny,d))
#벽이라면 종료
if rooms[nx][ny]==1:
print(ans)
exit()
print(ans)
이 문제에서 1 이 들어간 부분은 벽이기 때문에 청소를 해준 칸은 1과는 다른 숫자를 넣어주어 구별을 해주어야 한다.
왜냐하면 청소를 하기위해 전진하는 경우가 아니라면 청소를 이미 한 곳도 다시 방문 할 수 있기 때문이다.
생각해야할 조건들이 많아서 이것들을 하나하나 코드로 구현하는 부분이 어려웠
던 문제였다.
