단지번호붙이기
백준 2667
처음에는 DFS로 구현했었는데 메모리 초과가 나고 런타임 에러가 났다. 코드상의 문제일수도 있지만 대부분의 경우 BFS가 좀 더 효율적이므로 BFS로 구현했다.
from collections import deque
from collections import Counter
n = int(input())
home = [list(map(int, input())) for _ in range(n)]
queue = deque()
visited = [[0]*n for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y, cnt):
#넘겨받은 좌표의 값에 카운트를 대입하고, BFS방식대로 큐에 넣고 방문처리해준다.
home[x][y] = cnt
queue.append((x,y))
visited[x][y] = 1
while queue:
x,y = queue.popleft()
#상,하,좌,우 검사
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
#범위를 넘지않고 값이 1이고 방문하지 않았다면
if 0<=nx<n and 0<=ny<n and home[nx][ny]==1 and visited[nx][ny]==0:
#값을 넣어주고 큐에 넣고 방문처리.
home[nx][ny] = cnt
queue.append((nx,ny))
visited[nx][ny] = 1
#값이 1이고 방문하지 않았다면 카운트를 증가시키고 bfs를 호출한다.
cnt = 0
for i in range(n):
for j in range(n):
if home[i][j] == 1 and visited[i][j]==0:
cnt += 1
bfs(i,j, cnt)
# BFS연산이 모두 끝나고 0보다 큰 값만 새로운 리스트에 저장한다.
p = []
for i in range(n):
for j in range(n):
if home[i][j] > 0:
p.append(home[i][j])
print(cnt)
# Counter를 이용해 cnt값에 대한 빈도수를 구해주고 이를 오름차순 정렬 후 출력한다.
p = sorted(Counter(p).values())
for ele in p:
print(ele)
BFS : 넘겨받은 좌표값을 큐에 넣어주고 방문처리. -> 큐가 비어있지 않을 동안 큐에서 pop해서 pop한 값에 대한 이웃을 검사. -> 방문하지 않았다면 큐에 넣고 방문처리.
출력하는 부분에서 Counter가 아닌 set을 사용할 수도 있다.
p = []
for i in range(n):
for j in range(n):
if home[i][j] > 0:
p.append(home[i][j])
p2=[]
print(len(set(p)))
for ele in set(p):
p2.append(p.count(ele))
p2.sort()
for ele in p2:
print(ele)
set은 중복을 허용하지 않으므로, set(p)에 있는 원소를 p에서 카운트해서 p2리스트에 담은 후 정렬하고 출력한다.
collections 모듈의 Counter 클래스 사용법
21.07.01 다시 푼 결과
문제 조건 중 정렬해서 출력하는 것 빼먹지 말기
from collections import deque
n = int(input())
home = [list(map(int, input())) for _ in range(n)]
def bfs(x, y, home, visited, n):
queue = deque()
visited[x][y] = 1
cnt = 1
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n:
if visited[nx][ny] == 0 and home[nx][ny] == 1:
visited[nx][ny] = 1
cnt += 1
queue.append((nx, ny))
return cnt
visited = [[0]*n for _ in range(n)]
cnt = 0
ans = []
for i in range(n):
for j in range(n):
if home[i][j] == 1 and visited[i][j] == 0:
ans.append(bfs(i, j, home, visited, n))
cnt += 1
print(cnt)
ans.sort()
for ele in ans:
print(ele)
Author And Source
이 문제에 관하여(단지번호붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sezeom/단지번호붙이기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)