강의로 돌아가기
전현서

문제의 이해에 대한 내용

이 게시물은 문제의 접근을 도저히 못하고 계시는 분들이 보시면 좋을 것 같습니다.
일단은 문제 자체의 레벨이 좀 어려운 것 같습니다. 레벨2보다는 레벨3이 어울리는 문제입니다.

이 문제는 특별히 사용되는 알고리즘이 적용되는 문제는 아닙니다.
배열을 얼마나 잘 다루는 지에 대한 문제인 것 같습니다.

일단은 문제의 내용을 요약을 해보자면 빚을 임의의 위치에서 쐈을 때, S를 통과하면 직진
L을 통과하면 좌회전, R을 통과하면 우회전을 합니다. 또한 빛을 쏘는 위치가 그리드의 범위에 벗어나면
반대쪽으로 빛이 이동합니다. (가로 값이 제일 왼쪽에 있는 상태에서 또 빛을 왼쪽으로 쏜다고하면 오른쪽 끝에서 다시 빛을 받는다는 의미입니다. 세로도 마찬가지고요)
그래서 나온 사이클의 경우의 수를 전부 구해서 오름차순으로 답을 리턴 해주는 것이 문제입니다.

일단 어떻게 해서 사이클이 하나 발생하는 지에 대해 알 필요가 있습니다.
빛을 쏘면 빚은 SLR의 각각의 격자에 따라 어디론가 갈겁니다. 근데 이 문제에서 모든 사이클의 경우의 수를 구하라는거보면
분명 빛은 어디에서 쏘든 쐈던 위치로 되돌아온다는 의미가 됩니다. (안그러면 답을 못 구하기 때문이죠 ㅋㅋ)
물론 배열의 범위를 넘으면 반대편으로 되돌아오기 때문에 순환할 수 밖에 없는 구조가 되어집니다.
그럼 우리는 모든 사이클을 찾아서 각각의 사이클의 횟수를 구하고 그 값을 반환하면 됩니다.

일단 각각의 격자(grid)들이 가지고 있어야 하는 정보가 필요합니다. 없으면 빛이 어디로 가는지 알 방법이 없습니다.
이 배열은 격자를 가리키는 인덱스로도 접근이 가능한 배열이어야 접근이 편하겠죠.
즉, 각각의 격자들이 어떤 방향에서 빛을 쐈는지 확인해 줄 배열이 필요합니다.
빛을 쐈으면 1, 안 쐈으면, 0 이런 식으로 표시하는거죠.
빛은 문제에도 나왔다시피, 4방향으로 밖에 못 쏩니다. (즉, 대각선은 못 쏴요)
위, 아래, 오른쪽, 왼쪽 4방향이죠, 그럼 배열은 각각의 격자마다 4개의 데이터를 가지고 있으면 되겠죠?
기존에 grid는 2차원 배열이니까 빛이 이동한 경로 배열까지 더한 3차원 배열을 생성해줍니다.

그럼 이 경로 배열을 통해 빛이 이동한 경로를 확인할 수 있습니다. 임의의 위치부터 빛을 발사하여
다시 제자리로 돌아오면 한 싸이클이 만들어지고, 통과하지 않은 경로를 찾아 다시 사이클을 돌려서 경로를 모두 돌 때까지
반복하면 답은 자연스럽게 만들어지게 되어있습니다.

물론 배열 범위를 넘었을 경우 다시 원래 범위대로 정정 해야 하는 부분도 있어야겠죠.

뭐 그 이외에도 다른 부분도 있지만 그건 여러분이 충분히 구현하실 수 있을겁니다.
도움이 됐음합니다.

  • 정예준

    좀 이상하다 생각했는데 힌트가 되었네요 감사합니다!!

    정예준―2021.12.02 18:41
  • 윤창식

    레벨2 문제 풀어오다가 급당황했는데 도움이 되었어요!

    윤창식―2021.12.28 02:43
  • 백엔드맨

    문제이해를몬하겟어요..ㅠ

    백엔드맨―2022.03.24 04:09
  • 백엔드맨

    문제 이해했습니다.. 설명없이 이해하기 좀어렵네요.. 어떤식으로 발사하든 기존에 구해놓은 사이클을 조금이라도 침범한다면 그건 중복된 사이클이라는 의미네요

    백엔드맨―2022.03.24 04:38
  • 전현서

    오.. 좋습니다. 완벽하게 이해하셨군요.

    전현서―2022.03.24 07:59
  • 김태우

    크...글의 문체, 내용 모두 훌륭하시네요..

    김태우―2022.07.21 23:44
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.