백준 온라인 저지, BFS / 3055번: 탈출 (파이썬 / , 백준 골드문제)

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

제한

예제 입력 1

3 3
D.*
...
.S.

예제 출력 1

3

예제 입력 2

3 3
D.*
...
..S

예제 출력 2

KAKTUS

예제 입력 3

3 6
D...*.
.X.X..
....S.

예제 출력 3

6

예제 입력 4

5 4
.D.*
....
..X.
S.*.
....

예제 출력 4

4

힌트

W3sicHJvYmxlbV9pZCI6IjMwNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzhcdWNkOWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBhY1x1YzU0NVx1ZDU1YyBcdWM1NTRcdWQ3NTFcdWM3NTggXHVhZDcwXHVjOGZjIFx1Yzc3NFx1YmJmY1x1ZDYwMVx1Yzc0MCBcdWI0ZGNcdWI1MTRcdWM1YjQgXHViOWM4XHViYzk1IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWMxOTBcdWM1ZDAgXHViMTIzXHVjNWM4XHVhY2UwLCBcdWFkZjggXHViMmE1XHViODI1XHVjNzQ0IFx1YzJlNFx1ZDVkOFx1ZDU3NFx1YmNmNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZGZjXHVjYzk4XHVjNzU4IFx1ZDJmMFx1YjViMVx1YzIzMlx1YzVkMCBcdWQ2NGRcdWMyMThcdWI5N2MgXHVjNzdjXHVjNzNjXHVkMGE0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIzMlx1YzVkMFx1YjI5NCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWFjMDAgXHVkNTVjIFx1YjljOFx1YjlhYyBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHVjODFjXHVjNzdjIFx1Y2U1Y1x1ZDU1YyBcdWNlNWNcdWFkNmNcdWM3NzggXHViZTQ0XHViYzg0XHVjNzU4IFx1YWQ3NFx1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViZTY4XHViOWFjIFx1YjNjNFx1YjlkZFx1YWMwMCBcdWQ2NGRcdWMyMThcdWI5N2MgXHVkNTNjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmYwXHViNWIxXHVjMjMyXHVjNzU4IFx1YzljMFx1YjNjNFx1YjI5NCBSXHVkNTg5IENcdWM1ZjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0MCAmIzM5Oy4mIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWJiM2NcdWM3NzQgXHVjYzI4XHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc0MCAmIzM5OyomIzM5OywgXHViM2NjXHVjNzQwICYjMzk7WCYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWFkNzRcdWM3NDAgJiMzOTtEJiMzOTtcdWI4NWMsIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgJiMzOTtTJiMzOTtcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0IFx1YmQ4NFx1YjljOFx1YjJlNCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjEyNCBcdWNlNzggXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCkgXHViYjNjXHViM2M0IFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWQ2NTVcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4KFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMClcdWM3NDAgXHViYjNjXHVjNzc0IFx1Y2MyOFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YmIzY1x1YWNmYyBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHViM2NjXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWI4NWMgXHVjYzI4XHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHViYjNjXHViM2M0IFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWMxOGNcdWFkNzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJmMFx1YjViMVx1YzIzMlx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHVhYzAwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHViMmU0XHVjNzRjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWFjMDAgXHViYjNjXHVjNWQwIFx1YmU2MFx1YzljMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyZjBcdWI1YjFcdWMyMzJcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWJiMzhcdWM3OTBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmIzM5O0QmIzM5O1x1YzY0MCAmIzM5O1MmIzM5O1x1YjI5NCBcdWQ1NThcdWIwOThcdWM1MjlcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHVhYzAwIFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWFkNzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtLQUtUVVMmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTTElLQVIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBldmlsIGVtcGVyb3IgQ2FjdHVzIGhhcyBpbiBoaXMgcG9zc2Vzc2lvbiB0aGUgTWFnaWMgS2VnIGFuZCBoYXMgZmxvb2RlZCB0aGUgRW5jaGFudGVkIEZvcmVzdCEgVGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIG5vdyBoYXZlIHRvIHJldHVybiB0byB0aGUgQmVhdmVyJiMzOTtzIGRlbiB3aGVyZSB0aGV5IHdpbGwgYmUgc2FmZSBmcm9tIHRoZSB3YXRlciBhcyBxdWlja2x5IGFzIHBvc3NpYmxlISZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbWFwIG9mIHRoZSBFbmNoYW50ZWQgRm9yZXN0IGNvbnNpc3RzIG9mIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBFbXB0eSBmaWVsZHMgYXJlIHJlcHJlc2VudGVkIGJ5ICYjMzk7LiYjMzk7IGNoYXJhY3RlcnMsIGZsb29kZWQgZmllbGRzIGJ5ICYjMzk7KiYjMzk7IGFuZCByb2NrcyBieSAmIzM5O1gmIzM5Oy4gQWRkaXRpb25hbGx5LCB0aGUgQmVhdmVyJiMzOTtzIGRlbiBpcyByZXByZXNlbnRlZCBieSAmIzM5O0QmIzM5OyBhbmQgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGFyZSBzaG93biBhcyAmIzM5O1MmIzM5Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgbWludXRlIHRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBjYW4gbW92ZSB0byA0IG5laWdoYm91cmluZyBmaWVsZHMgKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KS4gRXZlcnkgbWludXRlIHRoZSBmbG9vZCBleHBhbmRzIGFzIHdlbGwgc28gdGhhdCBhbGwgZW1wdHkgZmllbGRzIHRoYXQgaGF2ZSBhdCBsZWFzdCBvbmUgY29tbW9uIHNpZGUgd2l0aCBhIGZsb29kZWQgZmllbGQgYmVjb21lIGZsb29kZWQgYXMgd2VsbC4gTmVpdGhlciB3YXRlciBub3IgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGNhbiBwYXNzIHRocm91Z2ggcm9ja3MuIE5hdHVyYWxseSwgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGNhbm5vdCBwYXNzIHRocm91Z2ggZmxvb2RlZCBmaWVsZHMsIGFuZCB3YXRlciBjYW5ub3QgZmxvb2QgdGhlIEJlYXZlciYjMzk7cyBkZW4uPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwsIGdpdmVuIGEgbWFwIG9mIHRoZSBFbmNoYW50ZWQgRm9yZXN0LCBvdXRwdXQgdGhlIHNob3J0ZXN0IHRpbWUgbmVlZGVkIGZvciB0aGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgdG8gc2FmZWx5IHJlYWNoIHRoZSBCZWF2ZXImIzM5O3MgZGVuLjxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgY2Fubm90IG1vdmUgaW50byBhIGZpZWxkIHRoYXQgaXMgYWJvdXQgdG8gYmUgZmxvb2RlZCAoaW4gdGhlIHNhbWUgbWludXRlKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMsIFIgYW5kIEMsIHNtYWxsZXIgdGhhbiBvciBlcXVhbCB0byA1MC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBSIGxpbmVzIHdpbGwgZWFjaCBjb250YWluIEMgY2hhcmFjdGVycyAoJiMzOTsuJiMzOTssICYjMzk7KiYjMzk7LCAmIzM5O1gmIzM5OywgJiMzOTtEJiMzOTsgb3IgJiMzOTtTJiMzOTspLiBUaGUgbWFwIHdpbGwgY29udGFpbiBleGFjdGx5IG9uZSAmIzM5O0QmIzM5OyBjaGFyYWN0ZXIgYW5kIGV4YWN0bHkgb25lICYjMzk7UyYjMzk7IGNoYXJhY3Rlci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNob3J0ZXN0IHBvc3NpYmxlIHRpbWUgbmVlZGVkIGZvciB0aGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgdG8gc2FmZWx5IHJlYWNoIHRoZSBCZWF2ZXImIzM5O3MgZGVuLiBJZiB0aGlzIGlzIGltcG9zc2libGUgb3V0cHV0IHRoZSB3b3JkICZsZHF1bztLQUtUVVMmcmRxdW87IG9uIGEgbGluZSBieSBpdHNlbGYuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- BFS를 활용해 물과 고슴도치의 위치를 상하좌우로 한칸씩 움직인다.
- 단 물부터 먼저 움직이고, 고슴도치를 움직이고, 매 초마다 동작하도록 한다.

코드

# https://www.acmicpc.net/problem/3055
# 접근방법
# BFS를 활용해 물과 고슴도치의 위치를 상하좌우로 한칸씩 움직인다.
# 단 물부터 먼저 움직이고, 고슴도치를 움직이고, 매 초마다 동작하도록 한다.
from collections import deque

r, c = map(int, input().split())
map_ = [[x for x in input()] for _ in range(r)]
hedgehog = deque([])
water = deque([])

for i in range(r):
    for j in range(c):
        if map_[i][j] == '*':
            water.append([i, j])
        elif map_[i][j] == 'S':
            hedgehog.append([i, j])
            map_[i][j] = 0
        elif map_[i][j] == 'D':
            x, y = i, j


def water_move():
    # 1초 마다 물 이동
    water_ = []
    while water:
        row, col = water.popleft()
        map_[row][col] = '*'
        for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            if 0<=row+dr<=r-1 and 0<=col+dc<=c-1:
                if map_[row+dr][col+dc] in ['.', 'S'] and [row_dr, col+dc] not in water_:
                    water_.append([row+dr, col+dc])
                    

    # 물을 다 이동시킨 뒤, 새로운 장소를 다시 water에 입력
    while water_:
        x = water_.pop()
        water.append(x)
    

def hedgehog_move():
    # 1초마다 고슴도치 이동
    hedgehog_ = []
    while hedgehog:
        row, col = hedgehog.popleft()
        for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            if 0<=row+dr<=r-1 and 0<=col+dc<=c-1:
                if map_[row+dr][col+dc] == '.' and [row+dr, col+dc] not in water:
                    hedgehog_.append([row+dr, col+dc])
                    map_[row+dr][col+dc] = map_[row][col] + 1
                elif map_[row+dr][col+dc] == 'D':
                    map_[row+dr][col+dc] = map_[row][col] + 1
                    return True

    # 고슴도치를 다 이동시킨 뒤, 새로운 자소를 다시 hedgehog에 입력
    while hedgehog_:
        x = hedgehog_.pop()
        hedgehog.append(x)

    return False

for time in range(1, 2501):
    if not hedgehog:
        break

    water_move()
    if hedgehog_move():
        break
if map_[x][y] == 'D':
    print('KAKTUS')
else:
    print(map_[x][y])