안녕하세요, H. 지뢰찾기 문제 출제자 이태윤입니다.
작년까지는 저도 알고스팟 모의고사에 참가하며 인터넷 예선을 준비했는데, 올해에는 출제를 하게 되었네요.
이 문제는 2006년 인터넷 예선 금고 문제에서 영감(?)을 받아서 만들게 되었습니다.
가장 빠른 Yes는 대회 시작 후 79분만에 stranger님이 받았습니다.
1. 문제 설명
문제가 한글이니 생략하겠습니다.
2. 문제 풀이
막상 처음 문제를 접하면 상당히 어렵게 느껴질 수 있는데, 문제의 특수한 조건을 이용하면 쉽게 방법을 찾을 수 있습니다.
특수한 조건이란 바로 U, D, L, R이 모두 서로 다른 수라는 것입니다. 이것을 이용하면 (1,2)와 (2,1)에 지뢰 존재 여부를 알 수 있습니다.
우선 (1,1)의 위험도를 봅시다. 이 수치는 4가지가 가능합니다.
A. (1,2)와 (2,1)에 둘 다 지뢰가 없다. -> 0
B. (1,2)에는 지뢰가 없고, (2,1)에는 지뢰가 있다. -> L
C. (1,2)에는 지뢰가 있고, (2,1)에는 지뢰가 없다. -> U
D. (1,2)와 (2,1)에 둘 다 지뢰가 있다. -> L+U
L과 U가 서로 다른 수이기 때문에, 우리는 (1,1)의 위험도를 보고, (1,2)과 (2,1)에 지뢰가 있는지 알 수 있습니다.
하지만 주변 두칸의 상황을 알아도, (1,1)에는 지뢰가 존재하는지 알 수 없습니다.
그래서 (1,1)에는 지뢰가 존재하는 경우와 지뢰가 존재하지 않는 경우로 나눠서 살펴봅니다.
(1,1) (1,2) (2,1) 에서 지뢰를 모두 제거하고나면, 다시 위와 같은 방법으로 (1,2)의 수치를 보고,
(1,3)과 (2,2)에 지뢰가 있는지 알 수 있습니다. 또 (2,1)의 수치를 보고, (2,2)와 (3,1)에 지뢰가 있는지도 알 수 있습니다.
이런 식으로 왼쪽 위부터 쭉 지뢰를 찾아가면 됩니다.
3. 소스 코드
Taeyoon_Lee
안녕하세요, H. 지뢰찾기 문제 출제자 이태윤입니다.
작년까지는 저도 알고스팟 모의고사에 참가하며 인터넷 예선을 준비했는데, 올해에는 출제를 하게 되었네요.
이 문제는 2006년 인터넷 예선 금고 문제에서 영감(?)을 받아서 만들게 되었습니다.
가장 빠른 Yes는 대회 시작 후 79분만에 stranger님이 받았습니다.
1. 문제 설명
문제가 한글이니 생략하겠습니다.
2. 문제 풀이
막상 처음 문제를 접하면 상당히 어렵게 느껴질 수 있는데, 문제의 특수한 조건을 이용하면 쉽게 방법을 찾을 수 있습니다.
특수한 조건이란 바로 U, D, L, R이 모두 서로 다른 수라는 것입니다. 이것을 이용하면 (1,2)와 (2,1)에 지뢰 존재 여부를 알 수 있습니다.
우선 (1,1)의 위험도를 봅시다. 이 수치는 4가지가 가능합니다.
A. (1,2)와 (2,1)에 둘 다 지뢰가 없다. -> 0
B. (1,2)에는 지뢰가 없고, (2,1)에는 지뢰가 있다. -> L
C. (1,2)에는 지뢰가 있고, (2,1)에는 지뢰가 없다. -> U
D. (1,2)와 (2,1)에 둘 다 지뢰가 있다. -> L+U
L과 U가 서로 다른 수이기 때문에, 우리는 (1,1)의 위험도를 보고, (1,2)과 (2,1)에 지뢰가 있는지 알 수 있습니다.
하지만 주변 두칸의 상황을 알아도, (1,1)에는 지뢰가 존재하는지 알 수 없습니다.
그래서 (1,1)에는 지뢰가 존재하는 경우와 지뢰가 존재하지 않는 경우로 나눠서 살펴봅니다.
(1,1) (1,2) (2,1) 에서 지뢰를 모두 제거하고나면, 다시 위와 같은 방법으로 (1,2)의 수치를 보고,
(1,3)과 (2,2)에 지뢰가 있는지 알 수 있습니다. 또 (2,1)의 수치를 보고, (2,2)와 (3,1)에 지뢰가 있는지도 알 수 있습니다.
이런 식으로 왼쪽 위부터 쭉 지뢰를 찾아가면 됩니다.
3. 소스 코드
15년 전