kisrin4319   2년 전

일반적인 bfs 알고리즘으로 문제를 해결하려 했습니다.

문제에 나와 있는 테스트 케이스는 올바르게 나오나 밑의 케이스 (11,11)의 경우 답은 4인데 제 코드로 돌리면 48이 자꾸 나와 수정하려고 했는데 도저히 모르겠습니다.

다른 분들의 질문 글을 보았는데 다른점이 있다면 29~35 Line 인것 같습니다. 다른 분들은 바로 큐에 집어넣었지만 저는 해당 조건마다 bfs 함수를 불러 해결하고자 했는데 잘못 된걸까요?

위의 방식과 다르게 현재 제 코드로는 어떻게 수정해야 될지 알려주셨으면 감사하겠습니다.

11 11
0 0 0 0 1 0 -1 -1 0 0 0 
0 -1 1 1 0 0 1 1 0 0 0 
0 0 0 0 -1 1 0 0 1 0 0 
0 0 -1 0 0 -1 -1 0 0 0 -1 
1 1 -1 0 0 1 0 0 0 -1 1 
-1 0 0 0 0 0 1 0 0 1 0 
0 1 0 -1 0 0 0 0 1 1 1 
0 0 0 1 0 0 0 0 0 -1 0 
0 0 0 0 0 0 0 0 0 0 -1 
-1 0 0 0 0 0 1 1 0 0 1 
-1 0 0 0 0 -1 -1 0 0 0 -1 

wowoto9772   2년 전

각 해당하는 칸에 토마토가 도달하는 최소 시간을 저장해주는 구조가 되야하지 않을까요???


010

000


111

010


111

212

kisrin4319   2년 전

흠.. 댓글을 읽고서 75라인을 ad[cx][cy] =1 대신에 ad[cx][cy]= ad[x][y]+1;  이런식으로 해서 행렬 전체를 확인해봤는데도 이상하게 나오네요 ㅠㅠ

wowoto9772   2년 전

전체 솔루션 코드좀 올려주세요 !!!!

kisrin4319   2년 전

이게 전체 소스 코드입니다!

wowoto9772   2년 전

다른 소스코드 부분은 모두 맞다고 가정하면,


66번째 라인이 문제가 되는 라인 같네요.


초기에 토마토가 놓여있는 위치가 시작점이 되어야 합니다

(초기에 토마토가 여러개라면 , 여러개의 위치가 동시에 시작점이 되도록 해야합니다.)


지금 솔루션을 보면,


0101

0000


1111

0100


1111

2120


1111

2123


이렇게 되는 것 같아요.

kisrin4319   2년 전

흠 그렇다면 for문을 돌려서 1이 등장하는 i,j 때마다 함수를 불러서 하는건 안되나보네요..
다른분들 처럼 바로 큐에 넣어서 해야되나봅니다 ㅠㅠ..

kdk8361   2년 전

최소값 제대로 나오나요? 나중에 들어간 1에서 더 빨리 도착하는 경우도 있을텐데요.

kisrin4319   2년 전

kdk8361 // 문제 아래에 있는 테스트 케이스는 제대로 나오지만 나머지 케이스는 잘 나오지 않는것 같습니다.

정올에서 돌려봤는데 accepted(30)이 나오는걸 보면 특정 케이스에서만 맞는거 같아요

kdk8361   2년 전

visited 대신 ad[cx][cy]와 ad[x][y]의 값을 비교해서 더 작은값이 들어가도록 하는 방법도 있습니다.

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