11967번 - 불켜기
1. BFS를 돌려서 베시가 그래프 내에 어디까지 도달할수 있는지 확인하는 문제가 아닙니다.
문제를 잘 읽어보시면 베시가 불을 켤수 있는 곳의 숫자를 세라는 문제입니다.
예를 들어서 3x3의 사이즈인 헛간에
(1,1)만 불이 켜진 상태에서 (1,1)에 (3,3) 스위치만 달려있다고 하면,
답은 (1,1), (3,3) 이렇게 두군데이므로 답은 2입니다.
이를 BFS 돌려서 방문가능한 셀을 찾으시려면 답이 1로 나올겁니다.
2. 때문에 굳이 BFS를 돌리지 않고
불을켠 곳, 방문할수 있는 거리(현재 있는 셀과 대상셀이 맨하탄 거리 기준 1)에 있었으나 불이 켜지지 않았어서 방문하지 못한곳만 잘 관리하셔도
AC를 받을 수 있습니다.
감사합니다 ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
k550706 3년 전 6
1. BFS를 돌려서 베시가 그래프 내에 어디까지 도달할수 있는지 확인하는 문제가 아닙니다.
문제를 잘 읽어보시면 베시가 불을 켤수 있는 곳의 숫자를 세라는 문제입니다.
예를 들어서 3x3의 사이즈인 헛간에
(1,1)만 불이 켜진 상태에서 (1,1)에 (3,3) 스위치만 달려있다고 하면,
답은 (1,1), (3,3) 이렇게 두군데이므로 답은 2입니다.
이를 BFS 돌려서 방문가능한 셀을 찾으시려면 답이 1로 나올겁니다.
2. 때문에 굳이 BFS를 돌리지 않고
불을켠 곳, 방문할수 있는 거리(현재 있는 셀과 대상셀이 맨하탄 거리 기준 1)에 있었으나 불이 켜지지 않았어서 방문하지 못한곳만 잘 관리하셔도
AC를 받을 수 있습니다.