unoffik   1달 전

알고리즘 공부를 시작한지 얼마 되지 않아서

제 소스가 어떤 방법(DFS? BFS? DP?)으로 푼지 모르겠는데,

답이 틀렸다고 하네요.

제공되는 샘플데이터랑 수동으로 입력했을땐 정상적으로 통과하는데

어떤 케이스가 안되는건지 찾기가 어렵네요.

혹시 보이시는 분 있으면 답글좀 달아주세요!


코드는 1,1에서 부터 시작해서 재귀적으로 방문가능한 모든 지점에 방문한 다음

방문한 적이 없거나 새로 방문한 값이 더 적을때 값을 업데이트 해줬습니다.

plzrun   1달 전

1. 배열 범위를 1부터 잡으셨으니까 배열 인덱스를 100이 아니라 101로 잡으셔야 합니다.

2. dfs로 해당 목표지점을 찾았을때 반드시 최소거리일 수 없어요. 그래서 dfs로 한 경우에는 모든 경로를 다 돌아야 하거든요.

다시말해서 a라는 경로로 n,m까지 먼저 탐색을 했는데 그게 최소거리는 아니잖아요? 그냥 먼저 땅을 밟은것일 뿐...

찾자마자 바로 최소거리임을 알 수 있는 방법은 bfs겠죠? 같은 depth에 있는걸 다 찾고 다음 depth로 넘어가니 찾은 값이 반드시 최소일수밖에 없어요.


만약 이 문제를 dfs로 풀려고 하신다면 N,M을 만났을때 반환하면 안됩니다.


3. 입력을 tmp로 받고 10으로 나누면서 값을 일일이 하나씩 받으셨는데, 일단 n,m사이즈가 100까지 됩니다. 100의자리 정수는 long long 타입으로도 담아낼 수가 없어요. 입력방법을 다르게 하셔야 합니다. 이런 경우는 string이나 char[]로 받거나 %1d를 써서 정수 하나씩 받는것을 추천드립니다.



아래 코드는 BFS로 짠 코드입니다.

원래 최소의 뭔가를 구해야 하는데 그래프 전체를 탐색해야하는 경우 bfs를 쓰면 됩니다.

dfs로도 짤 수 있긴한데 거의 완탐과 비슷하게 코드가 나와서 별로 좋지 않습니다.


plzrun   1달 전

윗 글 작성자입니다.


ㅎㅏ나더...


bool visit[100][100]={false};

위와 같이 쓰셨는데,

false저기에 하나만 쓴다고 해서 전체가 다 false로 초기화 되진 않습니다.

다만 전역변수로 선언하면 그건 data segment에 해당되기 때문에

컴파일시 data 세그먼트 영역은 0으로 밀립니다. 그래서 전부 false로 초기화된것처럼 느끼실 수 있었을 거에요.


그래서 로컬변수의 경우는 초기화 하지 않으면 쓰레기 값이 들어있는데 전역변수는 저렇게 나둬도 false나 0으로 초기화 되어있는 상태가 됩니다.


궁금하시다면 {true}로 바꿔보시고 출력해보시면 0번째 index만 바껴있는걸 확인하실 수 있을거에요.

물론 ,을 찍어도 마찬가지입니다.(0번째 index만 바껴있을거에요)



혹시 알고계셨다면 그냥 스킵 :D ㅎ


수고하세요~


unoffik   1달 전

답변이 정말 친절하시네요, 덕분에 이해가 잘 됐습니다.

말씀하신대로 인덱스를 101로하고 %1d를 입력받는걸로 바꾸니 통과됐습니다.

아직 dfs, bfs 개념을 정확하게 모르는데 올려주신 소스보고 bfs가 어떻게 동작하는지 좀 알거같네요.

감사합니다!

plzrun   1달 전

처음이시라면...


for(int z=0; z<sz; z++) <- 이 반복문이 약간의 테크닉?입니다. ㅎ (20번째줄)


큐 깊이 체크한다고 queue에 깊이를 넣어서 +1씩 한다면.. 메모리도 많이 먹고.. 또 다른방법으로 해도 메모리를 더 쓰는일을 피할수가 없는데요,

특히 bfs돌릴때 런타임에러가 난다면 배열 인덱스 잘못적어준게 아닌이상 십중팔구 queue가 터진거거든요. (BFS 단점이죠)


그런 큐를 쬐금 아껴줄수있는.. -_-; (어차피 저거 넣어서 터질 큐라면 원래 터졌겠지만..)

그리고 간단하게 해결할 수 있는 방법이 제가 방금전에 언급한 그 반복문이에요 ㅎ;



한가지 주의하실점은 sz값을 int sz = q.size();해서 미리 받았는데,

이걸 미리 받지 않고 저 반복문 안에다가 직접 써주면( for(int z=0; z<q.size(); z++) 이렇게 쓴다면 ) 이상하게 작동합니다.(queue 사이즈는 계속 변하니까.. ㅎㅎㅎ) 별 생각 없이 짜면 가끔 실수할 때가 있어요.


그럼 즐코딩하세요. :D ㅎ

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