오늘의 학습 키워드
DFS/BFS
공부한 내용 본인의 언어로 정리하기
- 문제에서 볼 수 있듯이, 주변 영역이 1인지 0인지를 확인하여 '연결', '단지'인지를 구할 수 있다. 그래서 주변영역부터 살펴보는 bfs를 사용하여 문제를 풀어보았다
어떤 문제가 있었고, 나는 어떤 시도를 했는지
첫번째 시도 -> 틀림
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
# graph = list(map(int,input().split()))
graph = [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 bfs(x,y):
queue = deque()
queue.append((x,y))
count =0
while queue:
x,y = queue.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if nx<0 or nx>=N or ny<0 or ny>=N:
continue
if graph[nx][ny]==1 and visited[nx][ny]==False:
queue.append((nx,ny))
visited[nx][ny] =True
count+=1
return count
for i in range(N):
for j in range(N):
if graph[i][j] == 1 and visited[i][j] == False:
answer.append(bfs(i,j))
# print(answer)
print(len(answer))
answer.sort()
for a in answer:
print(a)
-
앞뒤, 양옆의 숫자가 1인지 확인하기 위해 dx,dy 를 초기하였다
-
bfs 를 구성하여서, nx,ny 가 해당하는 범위가 아니면 continue 하고, 해당하는 범위면 queue 에 append 하고 방문으로 확인, count 수를 늘려주었다
-
하지만, 실패가 떠서 .... 질문 게시판에서 반례를 찾아보았다
-
입력
5
10101
01010
10101
01010
10101
- 출력
13
1
1
1
1
1
1
1
1
1
1
1
1
1
두번째 시도 -> 성공
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
# graph = list(map(int,input().split()))
graph = [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 bfs(x,y):
queue = deque()
queue.append((x,y))
visited[x][y]=True
count =1
while queue:
x,y = queue.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0 <= nx < N and 0 <= ny < N: # 유효한 좌표인지 확인
if graph[nx][ny] == 1 and not visited[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = True
count += 1
return count
for i in range(N):
for j in range(N):
if graph[i][j] == 1 and visited[i][j] == False:
answer.append(bfs(i,j))
# print(answer)
print(len(answer))
answer.sort()
for a in answer:
print(a)
- 첫번째 코드에서 수정한 부분
1) visited[x][y]=True
2) count =1
3) 조건문 수정
if 0 <= nx < N and 0 <= ny < N: # 유효한 좌표인지 확인
if graph[nx][ny] == 1 and not visited[nx][ny]:- 내가 간과한 것은 처음에도 visited 에 True 로 바꾸어줘야하는 부분
- 그러면서 count =1 로 시작해야하는 부분이었다
- 그리고 조건문을 조금 더 간단하게 수정하였다
