2주차 개념강의 당근마켓 문제

강사님 안녕하세요,

저도 강의 보다가 이부분 갸우뚱했는데요.

현재 코드상 visited 배열의 값을 그대로 출력하게 되어있는데요, 가령 (0,0) -> (1,0) 으로 이동하는 TC 를 입력하면 1칸만 이동 했음에도 불구하고 2라는 값을 출력하게 됩니다.

문제에서 "한칸" 움직일때 당근 1개를 소모하는 것이라고 했으므로, 출력은 visited 배열값에서 1을 뺀 값을 출력하는 것이 맞지 않을까 싶습니다.

원 질문자님 말씀대로 BFS 로직 구현과는 별도로 문제 해석에 따른 출력에 대한 질문이긴한데요,

출발지점(0,0)에 놓이는 것 자체만으로 가중치 1을 소모할 수는 없다고 보여집니다.

BFS 로 생성된 visited 배열을 출력해보면 아래와 같습니다.

1 0 5 0 9

2 3 4 0 8

0 0 5 6 7

0 0 6 7 8

0 0 7 8 9

안녕하세요 kim님 ㅎㅎ
네 수강생님 말씀이 맞습니다. ㅎㅎ

저게 문제에서 한칸, 두칸 이러면서 가중치와 정점을 혼용해서 문제를 내곤 하거든요.

예를 들어, a b c 라고 했을 때 a에서 c까지 갈 때 몇칸이 소모되냐? 라고 했을 때 답이 3칸 이런 문제도 있거든요.

처음에는 이런 문제들을 고려해서 이렇게 문제를 만들었는데

문제에서 "한칸" 움직일때 당근 1개를 소모하는 것이라고 했으므로

한칸 소모가 아니라 한칸을 움직일 때 소모하는게 맞으므로 수강생님 말씀이 맞습니다.

해당부분은 다음과 같이 수정했습니다.

맵의 세로길이 N과 가로길이 M 이 주어지고 이어서 N * M의 맵이 주어진다. 그 다음 줄에 승원이의 위치(y, x)와 당근마킷의 위치(y, x)가 주어진다. 이 때 승원이의 시작위치(y, x)에서 "당근한개"가 이미 소모된 상태로 본다.

감사합니다.