selgun05   6년 전


ttps://www.acmicpc.net/proble...

똑같은 문젠데

10번 이하로 뺄 수 있는지 없는지만 알아내는 문제인데 여기서는 정답나옵니다.

근데 이건 92%에서 틀렸습니다. 가 나오네요.


현재 코드는 틀린거로 나오고 

이유는 모르겠는데 map[10->12][10->12]로 선언하면 런타임오류 뜹니다. ... 11, 11까진 괜찮구요 메모리가 후달린가..?

째로1이 된걸 보면 10번 초과, 아닌건 구별가능한데 10번 미만으로 탐색이 될 때 횟수계산을 못하는 경우가 있다고 판단하고 있습니다.


기울이는 경우의 수는 처음엔 4가지, 그다음엔 방금 기울인 방향 기준 좌 우 두가지가 있다고 생각했구요.

구슬 움직이면서 경우의 수는

진행방향에서 두 구슬이 다른 줄에 있을 때 -> 들어간 거는 단순하게 따로 체크

진행방향에서 두 구슬이 한줄로 있을 때 -> 빨강공 먼저 or 파란공 먼저움직이는지 체크

이 때 둘다 들어가는지 하나만 들어가는지도 체크 했습니다.

각각 이프문으로 구별해낸 건 아닌데, state가 기본이 0으로 초기화한것, 공을 이동하는 순서를 두어서 파란공이 빠지면 -1이고 빨간공만 빠지면 1이 되게끔 구현했습니다.

(즉, <-, ->으로 움직일 때 R~~O~~B, R~~B~~O, O~~R~~B 에서 성공인지 실패인지 구별이 되게끔 했음 (제 생각엔))

도와주시면 정말 감사하겠습니다.

코드 설명 추가로 드리면

  1. 맵을 입력 받음, 맵에서 R B는 빈 통로문자인 . 으로 바꿈, 대신에 각 구슬의 위치를 구조체 xy r, b에서 기억함
  2. dfs를 할건데 처음으로 실행하기전 조건은 두 구슬중 하나라도 움직일 수 있으면 실행함, 조건에 맞는 동서남북 방향에 대해서 실행
  3. dfs내부에서 실행 조건(또 기울여야 하는 경우)은 길 탐색이 안끝난 경우(구슬이 안빠지거나, 움직일수 있거나, 기울인 횟수가 10번 미만인 경우)에 이전에 기울인 방향기준 좌, 우 방향으로 대해서 dfs를 재귀적으로 실행
  4. dfs내에선 3가지 state를 가짐, 성공, 탐색중, 실패.. ->성공, 실패인 경우 3. 조건에서 길 탐색이 끝난경우로 처리함 + 성공하면 성공까지의 기울임 횟수(suc_cnt)를 업데이트함

아 그리고 방향 값은 0 1 2 3이 서북동남 순입니다..

우, 좌는 +1더하고 +3더한거에서 4나눠서 계산했어요...

————————————————————-

혹시나해서 map을 12 by 12 로 세팅하고 벽으로 한바퀴 둘렀더니

해결됐습니다 이유는 모르겠네요

혹시 92%에서 틀리시는 분들 참고하시고 원인 아시는 분들은 알려주시면 감사하겠습니다

-----------------------------------------------

설마했는데 테스트케이스 문제였네요 해결됐습니다 -.,-..

댓글을 작성하려면 로그인해야 합니다.