c언어 길찾기 질문
글쓴이: 익명 사용자 / 작성시간: 토, 2020/06/06 - 1:33오전
0이 길이고 1이 돌인 맵에서 최단경로를 찾아 'X'로 표시하고 움직인 칸 갯수를 출력하는 함수입니다.
단, 그 뒤에 공간이 있을때 돌을 밀 수 있습니다. 돌이 두개 이상 연이어 있는 경우 돌을 밀 수 없습니다.
배열은 정수 배열이 아닌 문자로 했습니다.
row와 col은 각각 배열의 행과 열의 크기입니다. cnt는 움직인 횟수 입니다.
돌을 미는 부분을 열심히 생각해서 구현해봤는데 어떤 경우는 되고 어떤 경우는 안됩니다.ㅠㅠ
0001
1110
0000 -> 이땐 되구요
0000000
0111110
0111110
0100010
0101010
0101011
0001000 -> 이땐 되지 않습니다ㅠㅠ
오늘 내내 끙끙대고 있습니다 뭐가 문제인지 알려주세요...
int play(int x, int y) {
if (x < 0 || y < 0 || x >= row || y >= col) {
return 0;
} //주어진 범위 벗어남
else if (map[x][y] == '1') {
if (y < col - 1 && map[x][y - 1] == 'X' && map[x][y + 1] == '0') {
map[x][y] = '0';
map[x][y + 1] = '1';
return play(x, y);
} //돌 오른쪽으로 밀기
else if (x < row - 1 && map[x - 1][y] == 'X' && map[x + 1][y] == '0') {
map[x][y] = '0';
map[x + 1][y] = '1';
return play(x, y);
} //돌 아래쪽으로 밀기
else if (y > 0 && map[x][y + 1] == 'X' && map[x][y - 1] == '0') {
map[x][y] = '0';
map[x][y - 1] = '1';
return play(x, y);
} //돌 왼쪽으로 밀기
else if (x > 0 && map[x + 1][y] == 'X' && map[x - 1][y] == '0') {
map[x][y] = '0';
map[x - 1][y] = '1';
return play(x, y);
} //돌 위쪽으로 밀기
return 0;
} //돌 밟음
else if (x == row - 1 && y == col - 1 && map[x][y] == '0') {
map[x][y] = 'X'; cnt++;
return 1;
} //도착
else if (map[x][y] == '0') {
map[x][y] = 'X'; cnt++;
if (play(x, y + 1) || play(x + 1, y) || play(x - 1, y) || play(x, y - 1) == 1)
{
return 1;
}
map[x][y] = '0'; cnt--;
return 0;
} // 길
else {
return 0;
}
}Forums:
자세히 보지 않았는데 알고리즘 문제인 듯
알고리즘을 다시 점검해 보세요. 이를테면 막힌 데로 가서 돌을 밀 수 있는지 아닌지 보고 밀 수 있으면 밀고 계속 가보겠다는 거 같은데, 이 부분만 해도 이상합니다.
밀 수 있는 방향이 여럿이면, 여럿 다 밀어보고 다 실패하면 실패한 거고, 하나라도 되면 성공이죠.
%P.S.
수정합니다. 문제를 보니 동쪽으로 갈 때 막혀 있는데 동쪽에 공간이 있으면 밀고 갈 수 있다는 거 아닌가요? 동쪽의 돌을 북쪽이나 남쪽으로 미는 게 허용 안 되는 것처럼 읽히는데 코드는 달라보이네요. 하여튼 알고리즘이 이상합니다. 코드 쓰시기 전에 알고리즘부터 확인해 보세요.
또 다 실패해서 리턴할 때, 밀어놨던 돌은 되돌려 놓고 리턴해야 하는 거 같은데 얼핏 봐선 그런 코드가 안 보이네요.
검색을 할 때 갔던 곳과 돌로 막힌 곳은 구분되어야 할 것 같습니다. 돌로 막힌 곳은 일단 가서 밀어보려고 시도할 수 있지만 한 번 방문했던 곳은 다시 갈 필요가 없죠. 그런데 이 구분이 코드를 1분간 훑어 보니 안 보이네요.
코드를 올리신 것은 그대로 두시되 윗쪽에 pseudo code로 알고리즘을 올려 보세요. 그리고 그게 되는지 주어진 예에서 한 번 생각해 보시고요.
if (y < col - 1 && map[x][y -
if (y < col - 1 && map[x][y - 1] == 'X' && map[x][y + 1] == '0')
이 부분이 지금 위치가 돌위에 있는 상태인데 왼쪽이 방금 지나온 길 'X'이고, 오른쪽이 빈공간 '0'이라면
'1'을 오른쪽으로 민 뒤에 '0'이 된 이 자리에서 플레이를 시작하겠다.
라는 뜻으로 적은 코드인데 알고리즘이 이상한가요? ㅠㅠ 제가 c언어 처음 배워서 알고리즘이나 자료구조같은 것도 잘 모르는데 과제로 너무 어려운게 나와서 정말 힘드네요...
...
저는 질문자 분의 알고리즘을 자세히 보지 않았습니다. 다만, 그 위에 보면 map[x][y] == 1 인 경우에 이거저거 해보겠다는 대목이 있고 말씀하신 if는 그 중 하나죠. 그 얘기는 이미 현재 위치가 돌이 있는 자리란 거죠? 어디에서 돌이 있는 자리로 들어왔는지, 그 정보는 이 call stack에는 보존되어 있지 않습니다. 동서남북 어디에서 이리로 들어왔는지 그 정보가 없어진 걸로 보입니다. 그러니까 여기서 동서남북 어느 쪽으로 돌을 밀쳐낼지 알 수가 없죠. 마찬가지로 그 if 안에 call을 해서 온 return 값을 return하는데... 움직인 돌을 돌려놓지 않고 나가기도 하고, return 값이 정확해 보이지도 않습니다.
로직은 잘 이해가 안되지만 현재 play()가
로직은 잘 이해가 안되지만 현재 play()가 재귀함수로 불리는데, 재귀함수 사용은 디버그를 매우 어렵게 합니다.
차라리 goto 문으로 제일 위로 올라가서 다시 시작하는 것이 쉬운 접근이 아닐까 싶습니다.
이 문제는
recursion으로 푸는 게 맞다고 생각합니다. 최소한 recursion을 선택한 부분이 잘못된 것은 아닌 듯 보이는데, base case와 recursive step을 잘못 생각하고 있는 게 문제 같네요.
그냥
생각했던 것보다 알고리즘이 어렵군요. ;;;
대충 아래와 같이 됩니다.
밀고 n이라는 지점에 들어가서 목적지에 도달하지 못했다 해도, 그 서치에서 밟았던 자리가 실제 답의 일부가 될 수도 있다는 점이 좀 어렵네요.
search(x): mark(x, visited) if x is goal: return true, 0 for n in x.neighbors: if !visited(n): if !stone(n): success, length = search(n) if success: return success, length + 1 else: continue if !pushable(n): continue // this is stone, pushable, and not visited push() success, length = search(n) if success: return success, length + 1 restore() // continue to the next neighbor, i.e. another n // if not returned in the loop, this means failure // but.. as x failing does not mean no path from x at all, // remove x from the visited set unmark(x, visited); return false, -1댓글 달기