https://www.acmicpc.net/problem/29721
29721번: 변형 체스 놀이 : 다바바(Dabbaba)
첫 번째 줄에 체스판의 크기 $N$과 다바바의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000;$ $1 \le K \le \min(N^2, 100\,000))$ 두 번째 줄부터 $K+1$번째 줄까지 다바바의 위치 $X, Y$가 공백으
www.acmicpc.net
소스코드
풀이
★ 처음에 그래프로 다바바가 갈 수 있는 위치를 체크해서 결과를 출력하려고 했습니다. 근데 입력 값인 n의 범위가 10만까지 들어오기 때문에 10만 x 10만의 그래프를 그리면 시간초과가 발생하게 됩니다.
★ 두번째로는 리스트로 다바바가 갈 수 있는 위치를 확인하려고 했습니다. 하지만 리스트 안에서 기물이 갈 수 있는 위치를 체크하고, 이미 기물이 존재하는 위치인 경우까지 확인하려고 했기에 시간초과가 또 발생 ㅠㅠ
★ 마지막으로 딕셔너리를 이용한 풀이를 시도했습니다. 기물이 갈 수 있는 위치를 찾는 방법은 똑같습니다. 상하좌우로 2칸씩 이동하면서 체스판을 벗어나지 않는다면 일단 다바바가 갈 수 있는 위치입니다. 이 때 이미 기물이 존재하는 곳은 가지 못하기 때문에 입력으로 기물의 위치를 받을 때 그 위치를 -1로 체크해뒀습니다.
★ 그 후 상하좌우 탐색을 하면서 해당 위치가 -1이 아니라면 즉, 갈 수 있는 칸이면 1로 체크해줬습니다.
★ 마지막으로 딕셔너리를 돌면서 값이 1인 key를 찾으며 cnt를 출력해줍니다 :)
'Algorithm > 2023 브실컵' 카테고리의 다른 글
| [백준 알고리즘] 29725번: 체스 초보 브실이 (Python) (0) | 2023.11.08 |
|---|---|
| [백준 알고리즘] 29731번: 2033년 밈 투표 (Python) (0) | 2023.11.08 |
| [백준 알고리즘] 29719번: 브실이의 불침번 근무 (Python) (0) | 2023.11.07 |
| [백준 알고리즘] 29724번: '사과상자'에 들어있는 것은 무엇? 현금? (Python) (0) | 2023.11.07 |
| [백준 알고리즘] 29720번: 그래서 님 푼 문제 수가? (Python) (0) | 2023.11.07 |