백준 온라인 저지, DFS / 13565번: 침투 (파이썬 / , 백준 실버문제)

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

(a) The current percolates.	(b) The current does not percolate.

예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.

입력

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.

그렇지 않으면 NO를 출력한다.

제한

예제 입력 1

5 6
010101
010000
011101
100011
001011

예제 출력 1

NO

예제 입력 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

힌트

W3sicHJvYmxlbV9pZCI6IjEzNTY1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZTY4XHVkMjJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzhcdWM4MWNcdWIzMDBcdWQ1NTlcdWFkNTAgXHVjMGRkXHVkNjU0XHVkNTU5XHVjNWYwXHVhZDZjXHVjMmU0XHVjNWQwIFx1YzdhY1x1YzljMVx1YzkxMVx1Yzc3OCZuYnNwO1x1YzExZFx1YWQ1MFx1YzIxOFx1YjI5NCBcdWM4MDRcdWI5NThcdWFjMDAgXHVjZTY4XHVkMjJjKHBlcmNvbGF0ZSkgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTJjXHVjNzIwIFx1YmIzY1x1YzljOFx1Yzc0NCBcdWFjMWNcdWJjMWNcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMTJjXHVjNzIwIFx1YmIzY1x1YzljOFx1Yzc0MCAyXHVjYzI4XHVjNmQwIE0mbmJzcDsmdGltZXM7IE4gXHVhY2E5XHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwO1x1ZDNiOFx1Yzc1OFx1YzBjMSAyXHVjYzI4XHVjNmQwIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNhYmRcdWM3NDQgXHViYzE0XHVhZTY1XHVjYWJkKG91dGVyIHNpZGUpLCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3NDQgXHVjNTQ4XHVjYWJkKGlubmVyIHNpZGUpXHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWFjMDEgXHVhY2E5XHVjNzkwXHViMjk0IFx1YWM4MFx1Yzc0MFx1YzBjOSBcdWM1NDRcdWIyYzhcdWJhNzQgXHVkNzcwXHVjMGM5XHVjNzc4XHViMzcwLCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3NDAgXHVjODA0XHViOTU4XHViOTdjIFx1Y2MyOFx1YjJlOFx1ZDU1OFx1YjI5NCBcdWJiM2NcdWM5YzhcdWM3ODRcdWM3NDQgXHViNzNiXHVkNTU4XHVhY2UwIFx1ZDc3MFx1YzBjOVx1Yzc0MCBcdWM4MDRcdWI5NThcdWFjMDAgXHVkMWI1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjNjXHVjOWM4XHVjNzg0XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjODA0XHViOTU4XHViMjk0IFx1YzEyY1x1YzcyMCBcdWJiM2NcdWM5YzhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YmMxNFx1YWU2NVx1Y2FiZCBcdWQ3NzBcdWMwYzkgXHVhY2E5XHVjNzkwXHViNGU0XHVjNWQwIFx1YWNmNVx1YWUwOVx1YjQxOFx1YWNlMCwgXHVjNzc0XHVkNmM0XHVjNWQwXHViMjk0IFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMFx1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkNzcwXHVjMGM5IFx1YWNhOVx1Yzc5MFx1YjRlNFx1Yjg1YyBcdWM4MDRcdWIyZWNcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTQwIFx1YWQ1MFx1YzIxOFx1YWMwMCBcdWFjMWNcdWJjMWNcdWQ1NWMgXHVjMTJjXHVjNzIwIFx1YmIzY1x1YzljOFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQmbmJzcDtcdWM4MTVcdWJjZjRcdWFjMDAgMlx1Y2MyOFx1YzZkMCBcdWFjYTlcdWM3OTAgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YmMxNFx1YWU2NVx1Y2FiZFx1YzVkMFx1YzExYyBcdWQ3NThcdWI4MjQgXHVjOTAwIFx1YzgwNFx1Yjk1OFx1YWMwMCBcdWM1NDhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjZTY4XHVkMjJjXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1ZDMxMFx1YjJlOFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZVwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMzU2NVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjNweDsgd2lkdGg6MTI5cHhcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMzU2NVwvMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTdweDsgd2lkdGg6MTI3cHhcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPihhKSBUaGUgY3VycmVudCBwZXJjb2xhdGVzLjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPihiKSBUaGUgY3VycmVudCBkb2VzIG5vdCBwZXJjb2xhdGUuPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBGaWd1cmUgMShhKSBcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYzE0XHVhZTY1XHVjYWJkXHVjNWQwXHVjMTFjIFx1YWNmNVx1YWUwOVx1YjQxYyBcdWM4MDRcdWI5NThcdWFjMDAmbmJzcDtcdWM1NDhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjZTY4XHVkMjJjXHVkNTU4XHVjOWMwXHViOWNjLCBGaWd1cmUgMShiKVx1YzVkMFx1YzExY1x1YjI5NCBcdWFkZjhcdWI4MDdcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAmbmJzcDtNICgyICZsZTsgTSAmbGU7IDEsMDAwKSZuYnNwO1x1YWNmYyBOICgyICZsZTsgTiAmbGU7IDEsMDAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBNXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYywgTlx1YWMxY1x1Yzc1OCAwIFx1YjYxMFx1YjI5NCAxIFx1Yzc3NCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMFx1Yzc0MCBcdWM4MDRcdWI5NThcdWFjMDAgXHVjNzk4IFx1ZDFiNVx1ZDU1OFx1YjI5NCBcdWQ3NzBcdWMwYzksIDFcdWM3NDAmbmJzcDtcdWM4MDRcdWI5NThcdWFjMDAgXHVkMWI1XHVkNTU4XHVjOWMwJm5ic3A7XHVjNTRhXHViMjk0Jm5ic3A7XHVhYzgwXHVjNzQwXHVjMGM5IFx1YWNhOVx1Yzc5MFx1Yzc4NFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYzE0XHVhZTY1XHVjNWQwXHVjMTFjIFx1ZDc1OFx1YjgyNFx1YzkwMCBcdWM4MDRcdWI5NThcdWFjMDAgXHVjNTQ4XHVjYWJkXHVhZTRjXHVjOWMwIFx1Yzc5OCBcdWM4MDRcdWIyZWNcdWI0MThcdWJhNzQgWUVTXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTM1NjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJjb2xhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+UHJvZmVzc29yIEtpbSBpcyBpbiB0aGUgcHJvY2VzcyBvZiBkZXZlbG9waW5nIGEgbmV3IGZhYnJpYyBtYXRlcmlhbCBzdWNoIHRoYXQgdGhlIGVsZWN0cmljYWwgY3VycmVudCBwZXJjb2xhdGVzLiBUaGUgY3Jvc3Mgc2VjdGlvbiBvZiB0aGUgbmV3IGZhYnJpYyBjYW4gYmUgc2hvd24gaW4gdGhlIHR3by1kaW1lbnNpb25hbCBNICZ0aW1lczsgTiBncmlkLiBXZSBhc3N1bWUgdGhhdCB0aGUgdG9wIG9mIHRoZSBncmlkIGlzIHRoZSBvdXRlciBzaWRlIG9mIHRoZSBmYWJyaWMgYW5kIHRoZSBib3R0b20gaXMgdGhlIGlubmVyIHNpZGUuIFRoZSBibGFjayBjb2xvcmVkIGNlbGwgaW5zdWxhdGVzIHRoZSBjdXJyZW50IHdoaWxlIHRoZSB3aGl0ZSBjZWxsIGNvbmR1Y3RzIHRoZSBjdXJyZW50LiBUaGUgY3VycmVudCB0cmF2ZWxzIGZyb20gdGhlIG91dGVyIHNpZGUgdG8gdGhlIGlubmVyIHNpZGUgb2YgdGhlIGZhYnJpYyBvbmx5IHRocm91Z2ggdGhlIHdoaXRlIGNlbGxzIHRoYXQgYXJlIGFkamFjZW50IHRvIGVhY2ggb3RoZXIuIFdoZW4gdGhlIHdoaXRlIGNlbGxzIGFyZSBjb25uZWN0ZWQgZGlhZ29uYWxseSwgdGhlIGN1cnJlbnQgY2Fubm90IGZsb3cgKHNlZSBGaWd1cmUgMSkuIFRoZSBwcm9mZXNzb3Igd2FudHMgdG8gdGVzdCB3aGV0aGVyIHRoZSBjdXJyZW50IGNvdWxkIHBlcmNvbGF0ZSBmcm9tIHRoZSBvdXRlciBzaWRlIHRvIHRoZSBpbm5lciBzaWRlIHRocm91Z2ggdGhlIG1hdGVyaWFsIG9yIG5vdC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBmb2xsb3dpbmcgRmlndXJlIDEoYSkgc2hvd3MgdGhhdCB0aGUgY3VycmVudCBwZXJjb2xhdGVzIHRocm91Z2ggdGhlIG1hdGVyaWFsIGJ1dCBGaWd1cmUgMShiKSBkb2VzIG5vdDo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGVcIiBzdHlsZT1cIndpZHRoOjEwMCVcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMzU2NVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjNweDsgd2lkdGg6MTI5cHhcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEzNTY1XC8yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1N3B4OyB3aWR0aDoxMjdweFwiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4oYSkgVGhlIGN1cnJlbnQgcGVyY29sYXRlcy48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPihiKSBUaGUgY3VycmVudCBkb2VzIG5vdCBwZXJjb2xhdGUuPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gVHdvIGV4YW1wbGVzLjxcL3A+XHJcblxyXG48cD5XaGVuIHRoZSBpbmZvcm1hdGlvbiBvbiBlYWNoIGNlbGwgaXMgZ2l2ZW4sIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHdoZXRoZXIgdGhlIGN1cnJlbnQgY2FuIHBhc3MgdGhyb3VnaCB0aGUgbWF0ZXJpYWwgb3Igbm90LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBNICgyICZsZTsgTSAmbGU7IDEsMDAwKSBhbmQgTiAoMiAmbGU7IE4gJmxlOyAxLDAwMCkgd2hpY2ggcmVwcmVzZW50IHRoZSBzaXplIG9mIHRoZSBmYWJyaWMuIEluIHRoZSBmb2xsb3dpbmcgTSBsaW5lcywgdGhlIGluZm9ybWF0aW9uIGFib3V0IGVhY2ggY2VsbCBpcyBnaXZlbi4gRWFjaCBsaW5lIGNvbnNpc3RzIG9mIE4gY2hhcmFjdGVycyB3aGljaCBjb21wb3NlZCBieSAmbHNxdW87MCZyc3F1bzsgb3IgJmxzcXVvOzEmcnNxdW87LiBUaGUgY2hhcmFjdGVyICZsc3F1bzswJnJzcXVvOyByZXByZXNlbnRzIHRoZSBjb25kdWN0IGNlbGwgYW5kICZsc3F1bzsxJnJzcXVvOyByZXByZXNlbnRzIHRoZSBpbnN1bGF0ZSBjZWxsLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIElmIHRoZSBjdXJyZW50IGNhbiBwYXNzIHRocm91Z2ggdGhlIG1hdGVyaWFsIGZyb20gdGhlIHRvcCB0byB0aGUgYm90dG9tLCBwcmludCBZRVMuIElmIG5vdCwgcHJpbnQgTk8uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- DFS 탐색을 통해 첫번째 행에서 출발해 마지막 행에 도착하는지 판단한다.
- 만일 도착한다면 YES, 끝까지 도착하지 못한다면 NO를 출력한다.

코드

# https://www.acmicpc.net/problem/13565
# 접근 방법
# DFS 탐색을 통해 첫번째 행에서 출발해 마지막 행에 도착하는지 판단한다.
# 만일 도착한다면 YES, 끝까지 도착하지 못한다면 NO를 출력한다.
import sys
sys.setrecursionlimit(10**6)
def dfs(r, c):
    if r == m-1:
        return True
    for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0<=r+dr