{"id":857,"date":"2018-04-13T21:57:40","date_gmt":"2018-04-13T12:57:40","guid":{"rendered":"https:\/\/dong1lkim.oboki.net\/?p=857"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"baekjoon-online-judge-2178-%eb%af%b8%eb%a1%9c-%ed%83%90%ec%83%89","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/baekjoon-online-judge\/baekjoon-online-judge-2178-%eb%af%b8%eb%a1%9c-%ed%83%90%ec%83%89\/","title":{"rendered":"[BaekJoon Online Judge] 2178 \u2013 \ubbf8\ub85c \ud0d0\uc0c9"},"content":{"rendered":"<h1>[BaekJoon Online Judge] 2178 \u2013 \ubbf8\ub85c \ud0d0\uc0c9<\/h1>\n<h2>\ubb38\uc81c<\/h2>\n<p><a href=\"https:\/\/www.acmicpc.net\/problem\/2178\"><a href=\"https:\/\/www.acmicpc.net\/problem\/2178\">https:\/\/www.acmicpc.net\/problem\/2178<\/a><\/a><\/p>\n<p>N\u00d7M\ud06c\uae30\uc758 \ubc30\uc5f4\ub85c \ud45c\ud604\ub418\ub294 \ubbf8\ub85c\uac00 \uc788\ub2e4.<\/p>\n<table class=\"table table-bordered\" style=\"width:18%\">\n<tbody>\n<tr>\n<td style=\"width:3%\">1<\/td>\n<td style=\"width:3%\">0<\/td>\n<td style=\"width:3%\">1<\/td>\n<td style=\"width:3%\">1<\/td>\n<td style=\"width:3%\">1<\/td>\n<td style=\"width:3%\">1<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>\ubbf8\ub85c\uc5d0\uc11c 1\uc740 \uc774\ub3d9\ud560 \uc218 \uc788\ub294 \uce78\uc744 \ub098\ud0c0\ub0b4\uace0, 0\uc740 \uc774\ub3d9\ud560 \uc218 \uc5c6\ub294 \uce78\uc744 \ub098\ud0c0\ub0b8\ub2e4. \uc774\ub7ec\ud55c \ubbf8\ub85c\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, (1, 1)\uc5d0\uc11c \ucd9c\ubc1c\ud558\uc5ec (N, M)\uc758 \uc704\uce58\ub85c \uc774\ub3d9\ud560 \ub54c \uc9c0\ub098\uc57c \ud558\ub294 \ucd5c\uc18c\uc758 \uce78 \uc218\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624. \ud55c \uce78\uc5d0\uc11c \ub2e4\ub978 \uce78\uc73c\ub85c \uc774\ub3d9\ud560 \ub54c, \uc11c\ub85c \uc778\uc811\ud55c \uce78\uc73c\ub85c\ub9cc \uc774\ub3d9\ud560 \uc218 \uc788\ub2e4.<\/p>\n<p>\uc704\uc758 \uc608\uc5d0\uc11c\ub294 15\uce78\uc744 \uc9c0\ub098\uc57c (N, M)\uc758 \uc704\uce58\ub85c \uc774\ub3d9\ud560 \uc218 \uc788\ub2e4. \uce78\uc744 \uc140 \ub54c\uc5d0\ub294 \uc2dc\uc791 \uc704\uce58\uc640 \ub3c4\ucc29 \uc704\uce58\ub3c4 \ud3ec\ud568\ud55c\ub2e4.<\/p>\n<h2>\uc785\ub825<\/h2>\n<p>\uccab\uc9f8 \uc904\uc5d0 \ub450 \uc815\uc218 N, M(2 \u2264 N, M \u2264 100)\uc774 \uc8fc\uc5b4\uc9c4\ub2e4. \ub2e4\uc74c N\uac1c\uc758 \uc904\uc5d0\ub294 M\uac1c\uc758 \uc815\uc218\ub85c \ubbf8\ub85c\uac00 \uc8fc\uc5b4\uc9c4\ub2e4. \uac01\uac01\uc758 \uc218\ub4e4\uc740 \ubd99\uc5b4\uc11c \uc785\ub825\uc73c\ub85c \uc8fc\uc5b4\uc9c4\ub2e4.<\/p>\n<h2>\ucd9c\ub825<\/h2>\n<p>\uccab\uc9f8 \uc904\uc5d0 \uc9c0\ub098\uc57c \ud558\ub294 \ucd5c\uc18c\uc758 \uce78 \uc218\ub97c \ucd9c\ub825\ud55c\ub2e4. \ud56d\uc0c1 \ub3c4\ucc29\uc704\uce58\ub85c \uc774\ub3d9\ud560 \uc218 \uc788\ub294 \uacbd\uc6b0\ub9cc \uc785\ub825\uc73c\ub85c \uc8fc\uc5b4\uc9c4\ub2e4.<\/p>\n<h2>\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n<pre><code class=\"py\">def main():\n    n,m = map(int,input().split())\n    miro = []\n    for _ in range(n): miro.append(list(map(int,list(input()))))\n    visit = [[0 for _ in range(m)] for _ in range(n)]\n\n    dx,dy,q = [-1,1,0,0],[0,0,-1,1],[]\n\n    q.append((0,0))\n    visit[0][0] = 1\n\n    while 1:\n        x,y = q.pop(0)\n        if (x,y) == (n-1,m-1): break\n        for i in range(4):\n            t,v = x+dx[i],y+dy[i]\n            if t&gt;=0 and v&gt;=0 and t&lt;n and v&lt;m and visit[t][v]==0 and miro[t][v]==1:\n                q.append((t,v))\n                visit[t][v] = visit[x][y]+1\n\nif __name__ == '__main__': main()\n<\/code><\/pre>\n<p><code>bfs<\/code>\ub97c \uc774\uc6a9\ud574\uc11c \ud574\uacb0\ud55c\ub2e4. <code>dx<\/code>,<code>dy<\/code> \ub450 \ub9ac\uc2a4\ud2b8\ub85c 4\ubc29\uc704\ub97c \ud45c\ud604\ud558\uace0 \ub8e8\ud504\ub97c \ub3cc\ub9ac\uba74 \ucf54\ub4dc\ub97c \uc904\uc77c \uc218 \uc788\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[BaekJoon Online Judge] 2178 \u2013 \ubbf8\ub85c \ud0d0\uc0c9 \ubb38\uc81c https:\/\/www.acmicpc.net\/problem\/2178 N\u00d7M\ud06c\uae30\uc758 \ubc30\uc5f4\ub85c \ud45c\ud604\ub418\ub294 \ubbf8\ub85c\uac00 \uc788\ub2e4. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 \ubbf8\ub85c\uc5d0\uc11c 1\uc740 \uc774\ub3d9\ud560 \uc218 \uc788\ub294 \uce78\uc744 \ub098\ud0c0\ub0b4\uace0, 0\uc740 \uc774\ub3d9\ud560 \uc218 \uc5c6\ub294 \uce78\uc744 \ub098\ud0c0\ub0b8\ub2e4. \uc774\ub7ec\ud55c \ubbf8\ub85c\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[34,95],"class_list":["post-857","post","type-post","status-publish","format-standard","hentry","category-baekjoon-online-judge","tag-python","tag-95"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/857","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=857"}],"version-history":[{"count":2,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/857\/revisions"}],"predecessor-version":[{"id":1277,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/857\/revisions\/1277"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=857"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=857"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=857"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}