1189 컴백홈 문제 질문

10-Week C++ Coding Test | Algorithm Coding Test

Written on

405

안녕하세요

1189 컴백홈 문제 풀던 중 헷갈리는 것이 생겨 질문 올립니다.

http://boj.kr/1466145ff6884308af8686628e0cf03b

위 코드에서 변수 설정 부분에 int ny, nx를 전역 변수로 설정하면 틀리고,

int ny = y + dy[i];

int nx = x + dx[i];

지역 변수로 설정하면 답이 맞습니다.

왜 이런 일이 생기는지 설명해주실 수 있을까요?

C++코테 준비 같이 해요!

Answer 2

oort_cloud98

for (int i = 0; i < 4; i++)

{

ny = y + dy[i];

nx = x + dx[i];

if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;

if (visited[ny][nx] || map[ny][nx] == 'T') continue;

visited[ny][nx] = visited[y][x] + 1;

bt(ny, nx);

visited[ny][nx] = 0;

}

재귀함수 호출시 문제가 발생 합니답
nx, ny는 전역변수인데
재귀함수 블럭안에 있는 for문에서 nx, ny의 값을 직접 변경해줍니다.

nx, ny는 전역변수로 선언되어서 함수안에서 값이 바뀌면 함수 밖에서도 적용이 됩니다.
visited[ny][nx] = visited[y][x] + 1;

bt(ny, nx);

visited[ny][nx] = 0;

그렇게 됐을 때 해당 부분에서 에러가 발생합니다.
bt(순서 번호)라고 했을 때
bt(1) -> bt(2) -> bt(2)종료 -> bt(1) 종료 와 같이 함수가 실행 - 종료 됩니다.

(재귀함수는 도달할 수 있는 마지막 까지 도달 후 순차적으로 빠져나오게 됩니다 .
함수는 스택 메모리에 저장되어 순차적으로 실행 되기 때문입니다.)

해당 코드는 재귀함수 내에서 전역변수값이 계속 해서 변하는데 마지막 변한 값의 방문기록을 0으로 설정해서 값이 다르게 나옵니다.

조건문이 많아 글로 설명하기는 어렵고 로그를 찍어서 확인하는게 직관적일 것 같아 소스 코드 공유합니다.
http://boj.kr/01257c364adf4e629f6ebb1690378095