https:\/\/www.acmicpc.net\/problem\/7576<\/a><\/a><\/p>\n [BaekJoon Online Judge] 7576 – \ud1a0\ub9c8\ud1a0 \ubb38\uc81c https:\/\/www.acmicpc.net\/problem\/7576 \uc18c\uc2a4\ucf54\ub4dc bfs\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8\uac70\ub9ac \ubb38\uc81c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\ub2e4. \uc775\uc740 \ud1a0\ub9c8\ud1a0 \uc606\uc774\uba74 \uadf8 \ub2e4\uc74c \uc0ac\uc774\ud074\uc5d0 \uc775\uc740 \uc0c1\ud0dc\ub85c \ubc14\ub00c\uae30 \ub54c\ubb38\uc5d0, \ucd08\uae30 \uc0c1\ud0dc\uc5d0 \uc775\uc740 \ud1a0\ub9c8\ud1a0 \ubaa8\ub450\ub97c q\uc5d0 \ub123\uc740 \ub4a4 bfs \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud55c\ub2e4. \ud0d0\uc0c9\uc774 \ub05d\ub098\uba74 visit \ubc30\uc5f4\uc5d0\uc11c \uac00\uc7a5 \ub192\uc740 \uc22b\uc790\uac00 \uc0c1\uc790 \ub0b4\uc758 \ubaa8\ub4e0 \ud1a0\ub9c8\ud1a0\uac00 \uc775\ub294 \ucd5c\uc18c \ub0a0\uc9dc\uac00 \ub41c\ub2e4. from collections import […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,10],"tags":[34,95],"class_list":["post-898","post","type-post","status-publish","format-standard","hentry","category-baekjoon-online-judge","category-python","tag-python","tag-95"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/898","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=898"}],"version-history":[{"count":2,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/898\/revisions"}],"predecessor-version":[{"id":1347,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/898\/revisions\/1347"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=898"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=898"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n
bfs<\/code>\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8\uac70\ub9ac \ubb38\uc81c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\ub2e4. \uc775\uc740 \ud1a0\ub9c8\ud1a0 \uc606\uc774\uba74 \uadf8 \ub2e4\uc74c \uc0ac\uc774\ud074\uc5d0 \uc775\uc740 \uc0c1\ud0dc\ub85c \ubc14\ub00c\uae30 \ub54c\ubb38\uc5d0, \ucd08\uae30 \uc0c1\ud0dc\uc5d0 \uc775\uc740 \ud1a0\ub9c8\ud1a0 \ubaa8\ub450\ub97c q<\/code>\uc5d0 \ub123\uc740 \ub4a4 bfs<\/code> \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud55c\ub2e4. \ud0d0\uc0c9\uc774 \ub05d\ub098\uba74 visit<\/code> \ubc30\uc5f4\uc5d0\uc11c \uac00\uc7a5 \ub192\uc740 \uc22b\uc790\uac00 \uc0c1\uc790 \ub0b4\uc758 \ubaa8\ub4e0 \ud1a0\ub9c8\ud1a0\uac00 \uc775\ub294 \ucd5c\uc18c \ub0a0\uc9dc\uac00 \ub41c\ub2e4.<\/p>\nfrom collections import deque\n\ndx = [0,1,0,-1]\ndy = [1,0,-1,0]\n\nM,N = map(int,input().split())\nfield = [list(map(int,input().split())) for _ in range(N)]\n\nvisit = [[0 for _ in range(M)] for _ in range(N)]\n\nq = deque()\nfor i in range(N):\n for j in range(M):\n if field[i][j] == 1:\n q.append((i,j))\n visit[i][j] = 0\n\nwhile q:\n x,y = q.popleft()\n for i in range(4):\n to_x,to_y = x+dx[i],y+dy[i]\n if to_x>=0 and to_y>=0 and to_x<N and to_y<M:\n if field[to_x][to_y] == 0 and visit[to_x][to_y] == 0:\n q.append((to_x,to_y))\n visit[to_x][to_y] = visit[x][y] + 1\n\nripe = True\nfor i in range(N):\n for j in range(M):\n if field[i][j] == 0 and visit[i][j] == 0:\n ripe = False\n break\n\nif ripe:\n ans = 0\n for i in range(N):\n for j in range(M):\n if ans < visit[i][j]:\n ans = visit[i][j]\n print(ans)\nelse:\n print(-1)\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"