링크

빛의 경로 사이클

난이도

  • 프로그래머스 난이도 2
    • 모든 사이클을 확인하는방식을 진행하면된다.

문제요약

  • 방향이 적힌 격자가 있을때, 모든 진행방향에 대한 중복되지 않는 사이클 경로의 길이를 오름차순으로 출력하기

접근

    1. 모든 방향에서 빛을 쏘았을때 나오는 사이클을 확인하기
        • 위의 방식의 조건문을 좀더 줄여서 해보기

간단 알고리즘

  • 사이클확인 함수
    • 시작하는 x,y,방향di,사이클 중복확인용 save,행렬정보 grid를 입력으로 받는다.
    • count는 사이클의 길이 저장
    • S는 방향유지, L은 좌회전, R은 우회전으로 진행
      • x는 높이h가되면 0으로 -1은 h-1로, y는 너비 w가 되면 0으로 , -1이되면 w-1로 순환된다.
    • 저장용 dict자료형 save로 사이클의 중복 확인
      • format을 이용해 x-y-di를 key로 저장하여 해당 사이클이 있는지 확인한다.
    • 반복 시작
      • x-y-di가 save에 없으면 진행
        • save에 존재하면 break
        • 존재하다는것은 이미 해당 사이클은 존재한다는 의미 or 한바퀴 다돌았다는 의미가 된다.
      • grid[x][y]의 값을 확인, di에 따라 진행방향을 계산
      • count +1
    • count를 반환
  • 모든 경로 확인
    • 모든 grid의 위치에서 방향 4개를 전부 사이클확인 함수를 진행한다.
      • 0이면 해당 사이클은 이미 존재한 사이클
      • 0보다 크면 answer에 넣는다.
  • answer정렬
  • 좀더 조건문을 지우고싶을때
    • s,l,r도 조건, di도 조건문을 코드가 길어지는게 싫은경우
    • 배열을 이용
      • [srl방향,di] = [x증가,y증가,di]로 새로 배열을 만들어서 사이클 확인 함수에 활용하면 된다.
    • 조금 빨라진건가?

후기

  • 이거 월간코딩테스트에서 2시간내내 못풀고 손놓은 문제였다
  • 그대는 테스트케이스만 제대로 풀리고 제출하면 실패했나 그랬는데 이제와서 푸니 별로 오래걸리지도 않았다.
  • 하면서 format이라는 아주 좋은것을 알게되었다.
    • '{}-{}-{}'.format(x,y,z)
  • 조건문을 사용하기보다 배열을 이용해 푸는것을 자주보는것 같은데 이런식의 연습도 필요하다 생각했다.