백준 - 단지번호붙이기(#2667)
#BFS를 이용한 풀이
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
maps = [list(map(int,input().strip())) for _ in range(N)]
visited=[[0]*N for _ in range(N)]
answer=[]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def bfs(i,j):
queue = deque([[i,j]])
count=1
while queue:
x,y = queue.popleft()
for i in range(4):
nx,ny=x+dx[i],y+dy[i]
if nx<0 or ny<0 or nx>N-1 or ny>N-1:
continue
if not visited[nx][ny]:
if maps[nx][ny]==1:
visited[nx][ny]=1
count+=1
queue.append([nx,ny])
return count
for i in range(N):
for j in range(N):
if not visited[i][j]:
if maps[i][j]==1:
visited[i][j]=1
answer.append(bfs(i,j))
answer.sort()
print(len(answer))
for i in answer:
print(i)
#DFS를 이용한 풀이
import sys
input = sys.stdin.readline
N = int(input())
maps = [list(map(int,input().strip())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
answer=[]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def dfs(x,y):
global count
for i in range(4):
nx,ny=x+dx[i],y+dy[i]
if nx<0 or ny<0 or nx>N-1 or ny>N-1:
continue
if not visited[nx][ny]:
if maps[nx][ny]==1:
count+=1
visited[nx][ny]=True
dfs(nx,ny)
for i in range(N):
for j in range(N):
if not visited[i][j]:
if maps[i][j]==1:
visited[i][j]=True
count=1
dfs(i,j)
answer.append(count)
answer.sort()
print(len(answer))
for i in answer:
print(i)
- 백준 - 섬의 개수(#4963)
- 백준 - 치즈(#2638)
- 백준 - 점프 점프(#11060)
- 백준 - 나무 자르기(#2805)
- 백준 - 회의실 배정(#1931)
- 백준 - 단지번호붙이기(#2667)
- 백준 - 미로 탐색(#2178)
- 백준 - DFS와 BFS(#1260)
- 백준 - 가장 긴 증가하는 부분 수열(#11053)
- 백준 - 계단 오르기(#2579)
- 백준 - 유기농 배추(#1012)
- 백준 - 평범한 배낭(#12865)
- 소프티어 - 조립라인
- 소프티어 - 슈퍼컴퓨터 클러스터
- 프로그래머스 - 타겟넘버
- 프로그래머스 - 네트워크
- 프로그래머스 - 단속카메라
- 프로그래머스 - 올바른 괄호
- 프로그래머스 - 튜플
- 프로그래머스 - 여행 경로
- 프로그래머스 - 구명보트
- 프로그래머스 - 주차 요금 계산
- 프로그래머스 - 짝지어 제거하기
- 프로그래머스 - 예상 대진표
- 프로그래머스 - 멀리 뛰기
- 프로그래머스 - 단어 변환
- 프로그래머스 - 더 맵게
- 프로그래머스 - 기능 개발
- 프로그래머스 - 전화번호 목록
- 프로그래머스 - 베스트앨범
- 프로그래머스 - 위장
- 프로그래머스 - 전력망을 둘로 나누기
- 프로그래머스 - 모의고사
- 프로그래머스 - 야근 지수
- 프로그래머스 - 같은 숫자는 싫어
- 프로그래머스 - 소수 찾기
- 프로그래머스 - 프린터
- 프로그래머스 - 주식 가격
- 프로그래머스 - 다리 위를 지나는 트럭
- 프로그래머스 - 이중우선순위큐