알고리즘/programmers

[Programmers] 사라지는 발판

구데타마 2022. 6. 25. 02:30

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/92345

 

코딩테스트 연습 - 사라지는 발판

[[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4

programmers.co.kr

비트 마스킹을 연습하기 좋은 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 board 정보를 기반으로 boardBit을 생성합니다.

-> ex) [[1, 1, 1], [1, 0, 1], [0, 1, 1]]이 주어졌을 경우 boardBit는 111101011을 십진수로 변환한 값

2. 재귀함수 func는 매개변수 {y, x}에 위치한 사람이 플레이어의 턴일 때 최선의 플레이를 진행했을 경우 턴 수와 승리 여부를 반환하는 함수입니다.

2.1 {y, x}에 위치한 사람이 더 이상 움직일 수 없다면 패배

2.2 {y, x}에 위치한 사람이 상대방과 같은 발판에 서 있다면 승리

2.3 턴을 소비한 뒤 상대방의 관점에서 func함수 호출

2.3.1 상대방이 승리를 못할 경우 본인이 승리한다고 표시하고 최적의 턴 수를 업데이트

2.3.2 상대방이 승리했고 본인이 아직 승리하는 케이스가 없을 경우 최대 턴 수 업데이트

2.4 무조건 승리하는 경우 최적의 턴수와 함께 승리 여부를 true로 표시하고 반환

2.4.1 무조건 패배하는 경우 최대 턴수와 함께 승리 여부 false로 표시하고 반환

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형