학습 튜터
HSAT 1회 정기 코딩 인증평가 해설
- 등록일
- 2021-07-12
- 조회수
- 3246
안녕하세요. Softeer 운영 담당자 입니다. 지난 6월 26일, HSAT 정기 코딩 인증평가가 실시되었습니다. 주말에 운영됨에도 불구하고 많은 분들께서 관심을 가지고 참여하여 주셨습니다. HSAT는 각 문제의 모든 테스트케이스를 통과해야 정답으로 인정됩니다. 주어진 부분 문제는 코드의 정확성 및 효율성을 테스트하기 위함으로 부분 점수만 취득한 경우는 해당 정답으로 인정되지 않습니다. (아시는 바와 같이 입출력예제의 실행결과가 정답이라고 해서 그 문제의 모든 테스트케이스를 통과한 것은 아닙니다.) 두 문제를 모두맞춰 인증을 취득하신 분들께는 축하의 말씀을 전하고, 안타깝게 이번 인증을 취득하지 못하신 분들은 다음 인증평가에 좋은 결과 있길 바랍니다. 금번 평가문제는 연습문제를 통해 확인하실 수 있으며, 문제 해설과 풀이 방법을 공유하오니 역량을 키우는 데 조금이나마 도움이 되셨으면 좋겠습니다.
혹시 추가로 궁금하신 내용이 있으시면 자유롭게 Dev.Talk 게시판에 올려주세요! 향후 정기 인증평가 문제도 연습문제와 문제해설을 업로드 할 계획이니, 많은 관심을 가지고 인증평가에 참여해주시면 감사하겠습니다.
1. 차세대 지능형 교통시스템
풀이방법
BFS(Breadth-First-Search) 탐색을 통해 시간을 기준으로 상황을 시뮬레이션 하듯 풀이를 합니다 .
이 때, 각 교차로마다 입력값이 다르기에 해당 정보를 저장해놓고 현재 시간을 기준으로 내가 이동할 수 있는 방향을 조회합니다. 여기서 4가지 상태를 무한히 반복하므로 T%4 상황으로 정리할 수 있습니다.
하지만 사이클이 발생할 가능성이 있기에 방문처리가 필요합니다. T초 상황과 T+4초 상황일때 같은 방향에서 들어오는 경우라면, T+1초와 T+5초의 상황은 동일합니다.
즉, 같은 상황이 여러번 반복됨으로 불필요하게 탐색하지 않아도 되는 상황입니다.
그리하여 방문처리 check 배열(check[time][dir][x][y])을 두어 위의 불필요한 상황을 해결 할 수 있습니다.
마지막으로 방문했던 교차로를 찾기 위해 check 배열을 4중 for문을 통해 방문한 교차로를 카운트 해줍니다.
(교차로를 셀 때는 시간/방향은 문제가 되지 않음으로 고려하여 카운트합니다.)
2. 로봇이 지나간 경로
풀이방법
Case 1 경우, 모든 #들이 하나의 열 또는 하나의 행에 들어 있으므로, 이 행을 찾고, 칸 순서대로 방문하면 됩니다.
Case 2 부터는, A 명령이 로봇을 두 칸씩 앞으로 보내고, 한 번 방문한 칸은 다시 방문하지 않는다는 조건으로 인해, 입력으로 주어지는 사수의 경로는 반드시 아래와 같이 경로 외적인 이유로 붙어 있는 경우가 없습니다.
(불가능한 경우)
[1-9A-Z 순으로 방문순서 표시]
..1234567....
....CBA98....<-- 7 지점에서 A 명령으로 8과 9를 거칠 방법이 없음
....DEFGHI...
(가능한 경우)
..1234567....
........8....
...EDCBA9....<-- 이렇게 두 칸이 인접한 경우는 경로 상에서 인접한 경우밖에 없음
...F.........
...GHIJ......
따라서 입력만 봐도 로봇이 지나가야 하는 경로가 어떻게 생겼는지를 바로 알 수 있습니다.
맨 끝 지점에서 다른 쪽 끝 지점까지 #만을 타고 계속 따라가면 됩니다.
최초에 로봇을 어디에, 어떤 방향으로 놓을지 찾기
맨 끝 지점은,
· 자기 칸이 #이면서,
· 인접한 칸들 중 #가 정확히 한 개 있는지점
이러한 지점은 총 2개가 있으며, 조건문을 통해 로봇을 어떤 칸에 놓아야 하는지를 알 수 있습니다.
로봇의 방향의 경우, 로봇이 인접한 # 쪽을 향하게 놓아야 불필요한 회전을 하지 않습니다.
경로 따라가기
# 칸이 맨 끝 지점이 아니라면, 인접한 칸들 중 #는 정확히 두 개 일 것 입니다.
두 개 중 한 칸은 이미 지나온 칸이고, 나머지 한 칸이 아직 방문하지 않은 칸일 것입니다.
아직 방문하지 않은 칸으로 이동을 하면 됩니다.
다만 로봇은 방향을 가지기 때문에 회전에 대한 처리를 고민해야 합니다.
변수로 "현재 주인공이 바라보고 있는 방향" (direction)을 저장해 두고, 각 방향마다 "그 방향으로 이동하면 좌표가 어떻게 바뀌는지 계산해 둡니다(북→동→남→서).
이는 북쪽에는 0, 동쪽에는 1, 남쪽에는 2, 서쪽에는 3의 index를 대응시킨 것으로, 이러한 순서대로 방향을 숫자에 대응한 이유는 index를 1 증가하면 오른쪽으로 90도 회전, 1 감소시키면 왼쪽으로 90도 회전한 것으로 볼 수 있어서 처리가 용이하기 때문입니다.
매번 현재의 방향 (now_direction)과 다음 칸으로 이동하기 위해 봐야 하는 방향 (target_direction)을 비교하여 왼쪽 또는 오른쪽으로 회전하면 됩니다.