leeyh2006   4년 전

BFS로 (1,1)에서 (N,M) 가는 경로는 탐색해서 저장해 놨는데 전체적인 1의 개수 정보만 얻고 최단 경로를 얻지를 못하겠습니다..

어떻게 하면 될까요 ?


추가 질문 - 양 갈래 방향이 있을경우 어떤식으로 처리를 해야될까요 ?

plzrun   4년 전

bfs에서 깊이의 수를 세주면 됩니다.

약간의 테크닉이라고 할 수도 있는데,


bfs를 도는 queue의 사이즈를 체크해서 그 사이즈 만큼 똑같은 bfs를 돌고나면

카운트를 하나씩 해주는 겁니다.

그리고 다시 똑같이 큐 사이즈 재고 위에서 했던 것을 반복합니다.


코드는 아래와 같습니다.

leeyh2006   4년 전



밑에 있는 방식으로 
Que가 비어 있을때 까지 그 좌표 정보에 맞춰서  큐에 저장하고 길이를 추가시켜주고 ,(N,M)이 되는 시점에 빠져 나오게 코드를 짰는데 제 설계가 잘못된건가요 ?..

plzrun   4년 전

와 답변 길게 달았었는데 모르고 safari를 종료하는 바람에 다 날아갔네요 ㅠㅠ

그냥 짧게 말씀드릴게요.
앞으로는 전체 코드를 붙여주셨으면 해요. ㅎㅎ 부분만 보면 정확하게 답변해드리기가 힘들어요.
보통 틀릴때에는 본인이 생각하지 못한 부분에서 발생하는 경우가 많으니까...


적어주신 방법이 틀린건 아닌데, 코드에서 실수가 있으신거 같아요.

이 코드를 보면 in.l++이 잘못된거 같아요.
bfs깊이마다 증가가 돼야하는데, 인접한 정점을 들여다 볼때마다 계속 증가가 되고 있네요.
그리고 해당 방법으로는 p.x나 p.y가 절대 board범위를 벗어나지 않는다고 확신하고 계시는 것 같은데,
저는 잘 모르겠네요.. 돌다보면 튕겨져나가는 부분이 있을 수도 있고.. (안나간다면 다행이고)
그 부분은 assert()로 확인해보시는게 좋을것 같아요.
아니면 이런걸 미연에 방지하기 위해 위에 범위 체크하는 조건문을 다는 게 확실하겠죠.
(이미 전체 코드에 있을수도 있지만, 제가 지금 부분만 보고 있어서 하는 얘기 ㅎ)


그런데, 이런 bfs코딩은 너무 정형화 되어있어서
누가 짜도 저랑 90%가까이 일치하게 코딩할거에요.
그러니 제 코딩스타일 대로 전부 따라해보시고
모두 익히세요. bfs는 제가 작성한 코드와 같이 코딩하는게 답이에요.

모두 코딩 스타일이 다를 수 있지만,
leeyh님께서 작성하신 코드는 다르다는 범위를 벗어났어요.

예를들면, x*y도 x를 y번 더해서 구한 사람에게 답이 틀렸다 할 순 없지만,
그냥 x*y연산을 하지 x를 y번 더하는 사람은 없잖아요??
그런 의미에서 코딩스타일도 다른 코딩스타일이 아니라 틀린 코딩스타일이 존재한다고 생각해요.

혹여라도 기분나쁘게 생각하지 않으셨으면.. ^^
그리고 이미 알고계셨다면 그러려니 생각해주세요.

leeyh2006   4년 전

도움 많이 됬습니다 ~~ 감사합니다.


leeyh2006   4년 전

@plzrun 님 코딩 스타일로 자바에서 적용 해봤는데 결과 값이 이상하게 나와서요 ㅠㅠ

몇일 째 계속 하고 있는데 도저히 어디가 틀린지 모르겠어서 그런데 소스 한번 봐주실 수 있나요?

plzrun   4년 전

제가 자바는 잘 못해서 ㅠㅠ
근데 원인은 찾았어요.

자바는 C랑 다르게 변수가 모두 레퍼런스인거 같아요.

그니까 p에 (0,5)에 해당하는 좌표를 넣고 큐에 넣었는데,
그 p값을 (1,4)로 바꿔버리면 큐에 들어있는 (0,5)도 (1,4)로 바뀌는 것 같아요.

그렇게 되면, 문제에 나와있는 테스트케이스 첫번째꺼를 보면
(0,4)에서 원래 (0,5)랑 (1,4) 2개를 넣잖아요?
그런데 큐에는 (1,4)만 2개 있는게 되어버려요.
그럼 그래프 level을 씌워주는게 꼬여버리네요.

그래서 queue에 넣을때는 new Point() 형태로 해서 새로운 객체를 만들어 넣어주니까 해결이 됐어요~

plzrun   4년 전

아 그리고 제 코드 47번째줄에 보면 큐가 빌때까지 모두 비워준 다음에 break를 거는데요,

제가 자바에서는 코드를 바로 종료시키는 방법을 몰라서 저렇게 했어요.

물론 큐에서 한번 빠져나온 값은 이미 visit배열로 체크가 되어있어서 답 출력이후에 남은 정점들을 돌다가 문제가 생길일은 없겠지만,

굳이 애매하게 남길 필요는 없을 것 같아요.

leeyh2006   4년 전

@plzrun 아 그 문제라고는 생각을 못하고 있었네요 ㅠㅠ 설마설마 했는데 로직만 잘못된 줄 알고  .. 정말 감사합니다!

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