{"id":896,"date":"2019-04-07T13:26:41","date_gmt":"2019-04-07T04:26:41","guid":{"rendered":"https:\/\/dong1lkim.oboki.net\/?p=896"},"modified":"2019-09-01T22:23:15","modified_gmt":"2019-09-01T13:23:15","slug":"2667-%eb%8b%a8%ec%a7%80%eb%b2%88%ed%98%b8%eb%b6%99%ec%9d%b4%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/2667-%eb%8b%a8%ec%a7%80%eb%b2%88%ed%98%b8%eb%b6%99%ec%9d%b4%ea%b8%b0\/","title":{"rendered":"[BaekJoon Online Judge] 2667 &#8211; \ub2e8\uc9c0\ubc88\ud638\ubd99\uc774\uae30"},"content":{"rendered":"<h1>[BaekJoon Online Judge] 2667 &#8211; \ub2e8\uc9c0\ubc88\ud638\ubd99\uc774\uae30<\/h1>\n<h2>\ubb38\uc81c<\/h2>\n<p><a href=\"https:\/\/www.acmicpc.net\/problem\/2667\"><a href=\"https:\/\/www.acmicpc.net\/problem\/2667\">https:\/\/www.acmicpc.net\/problem\/2667<\/a><\/a><\/p>\n<h2>\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n<p>\uc9c0\ub3c4 \ub0b4\uc758 \ubaa8\ub4e0 \uc88c\ud45c\ub97c \ud0d0\uc0c9\ud558\uc5ec, \uc9d1\uc774 \ubc1c\uacac\ub420 \ub54c\ub9c8\ub2e4 \uadf8 \uc9d1\uc758 \uc88c\ud45c\ubd80\ud130 <code>dfs<\/code>\ub97c \uc774\uc6a9\ud574 \uc5f0\uacb0\ub41c \uc9d1\uc744 \ubaa8\ub450 \ucc3e\ub294\ub2e4. \uacc4\uc18d\ud574\uc11c \uc55e\uc758 \uacfc\uc815\uc744 \ubc18\ubcf5\ud558\ub294\ub370 \ub2e8\uc9c0 \ubc88\ud638\ub9cc \ud558\ub098\uc529 \ub298\ub824\uc8fc\uae30\ub9cc \ud558\uba74 \ud574\uacb0\ud560 \uc218 \uc788\ub2e4.<\/p>\n<pre><code class=\"py\">dx=[0,1,0,-1]\ndy=[1,0,-1,0]\nN = int(input())\ntown = [list(map(int,list(input()))) for _ in range(N)]\ndistrict = 1\ncnts,stack = [],[]\ndone = False\nwhile done == False:\n    for i in range(N*N):\n        if town[i\/\/N][i%N] == 1:\n            stack.append((i\/\/N,i%N))\n            district += 1\n            town[i\/\/N][i%N] = district\n            cnts.append(1)\n            break\n        if i == N*N-1:\n            done = True\n    while stack:\n        x,y = stack.pop(-1)\n        for i in range(4):\n            to_x,to_y = x+dx[i],y+dy[i]\n            if to_x&gt;=0 and to_y&gt;=0 and to_x&lt;N and to_y&lt;N:\n                if town[to_x][to_y] == 1:\n                    stack.append((to_x,to_y))\n                    town[to_x][to_y] = district\n                    cnts[len(cnts)-1] += 1\ncnts.sort()\nprint(len(cnts))\nfor i in range(len(cnts)):\n    print(cnts[i]) \n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>[BaekJoon Online Judge] 2667 &#8211; \ub2e8\uc9c0\ubc88\ud638\ubd99\uc774\uae30 \ubb38\uc81c https:\/\/www.acmicpc.net\/problem\/2667 \uc18c\uc2a4\ucf54\ub4dc \uc9c0\ub3c4 \ub0b4\uc758 \ubaa8\ub4e0 \uc88c\ud45c\ub97c \ud0d0\uc0c9\ud558\uc5ec, \uc9d1\uc774 \ubc1c\uacac\ub420 \ub54c\ub9c8\ub2e4 \uadf8 \uc9d1\uc758 \uc88c\ud45c\ubd80\ud130 dfs\ub97c \uc774\uc6a9\ud574 \uc5f0\uacb0\ub41c \uc9d1\uc744 \ubaa8\ub450 \ucc3e\ub294\ub2e4. \uacc4\uc18d\ud574\uc11c \uc55e\uc758 \uacfc\uc815\uc744 \ubc18\ubcf5\ud558\ub294\ub370 \ub2e8\uc9c0 \ubc88\ud638\ub9cc \ud558\ub098\uc529 \ub298\ub824\uc8fc\uae30\ub9cc \ud558\uba74 \ud574\uacb0\ud560 \uc218 \uc788\ub2e4. dx=[0,1,0,-1] dy=[1,0,-1,0] N = int(input()) town = [list(map(int,list(input()))) for _ in range(N)] district = 1 cnts,stack = [&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,10],"tags":[34,95],"class_list":["post-896","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\/896","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=896"}],"version-history":[{"count":2,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/896\/revisions"}],"predecessor-version":[{"id":1345,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/896\/revisions\/1345"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=896"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=896"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=896"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}