kiasu93   2년 전

que안에 좌표(x,y), 지나온 길(cnt), 벽을 뚫은 횟수(select) 이렇게 정보를 넣고

첫 좌표 -> 큐 삽입 , 방문처리

큐를 돌리면서 안에서 4방향 탐색시

select이 1이하 & 도착지점 도달이면 cnt 출력후 종료   -->>>>> 종료조건에 이르지 못하고 while문을 빠져나가면(que가 비면) -1출력후 종료

select이 1일떄 - 다음 지점이 1이면 continue   - 방문처리

                       - 다음 지점이 0 이면 큐에 삽입   - 방문처리

select이 0이면 - 다음지점 1이면 select 증가 큐 삽입 - 방문처리

                       - 다음지점 0이면 큐 삽입 - 방문처리 

위 과정에서 큐 삽입시에 cnt는 1씩 증가시켜줬습니다.

틀렸습니다가 뜨는데 혹시 로직 자체에 문제가 있을까요? ( 예제는 맞습니다)

추가적으로 질문검색 게시판을 읽고왔습니다

 단순 방문처리로 안된다 -> 벽을 부수고 진행했는지 부수지 않고 진행했는지를 판단해주기 위해 que에 select 변수로 판별했습니다

혹시 이런식으로 que에 정보를 넣지 않고 방문처리를 따로 해줘야하는게 있나요?

djm03178   2년 전

큐에 정보를 넣어줬는지가 중요한 게 아닙니다. 중요한 건, 같은 칸을 서로 다른 select에 대해 중복해서 방문할 수 있어야 된다는 것입니다. FAQ에도 써있지만, 어떤 칸에 select가 1인 상태에서 먼저 도달했다고 해서, 이후에 select가 0인 상태로 도달한 건 처리하지 않아도 괜찮을까요? select가 1일 때 그 지점을 지나쳤는데 만일 끝에 도달을 못 하고, 그 때까지 벽을 하나도 안 부순 상태여야만 끝에 도달할 수 있다면 어떻게 할 건가요?

onlyhim   2년 전

visit 배열을 2차원으로만 잡으면, 해당 정점을 방문했을때 벽을 부순 이력이 있는지 없는지 알수 없습니다.

kiasu93   2년 전

답변 주신 두분 감사합니다!

안그래도 반례를 찾아보다가 

벽을 뚫고 이미 방문했던 어떤 지점이지만 이 해당 이동은 결과적으로 도달할수 없을 때

다른 벽을 뚫지 않은 이동이 해당 지점에 도착하게 해야하는거였네요

방문 처리 배열을 visit[1001][1001][2] 이렇게 처리해서 풀었습니다!!

댓글을 작성하려면 로그인해야 합니다.