[알고리즘] 백준 2667

그냥 dfs 로도 풀어보고 bfs 로도 풀어봤다.
난 말하는 감자다 걍 어렵다 ㅋ
아직 알고리즘 포스팅을 쓰는 건 익숙하지 않으니 일단 기록하는게 목표다

문제 :
https://www.acmicpc.net/problem/2667

처음딱 문제를 봤을땐 하나를 찝어서 이웃된거 다 파고 들어가자 라는 생각에 dfs로 풀었다.

n = int(input())
arr_number = [] #단지수를 입력받는 배열
arr = []


for i in range(n):
    arr.append(list(map(int,input())))

def dfs(x,y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    
    if arr[x][y] == 1: #1일 경우에는 상하좌우를 검색할 것
        global count
        count += 1
        arr[x][y] = 0 #방문 처리해주기
        
        dfs(x,y-1) #좌
        dfs(x,y+1) #우
        dfs(x-1,y) #상
        dfs(x+1,y) #하
        return True
    return False

count = 0
result = 0

for i in range(n):
    for j in range(n): #각 노드 마다 검색할 것
        if dfs(i,j) == True:
            arr_number.append(count)
            count = 0 
            result += 1

arr_number.sort()
print(result)
for i in range(len(arr_number)):
    print(arr_number[i])

다양하게 풀면 좋자나? 문제에서 bfs dfs 다 쓸 수 있다길래 bfs 로도 풀었다.
문제에서 제시한 테스트 케이스는 맞게 나오길래 개좋아 하면서 제출했다 근데 왠걸 틀렸다. 아직 반례를 생각할 짬은 안된다 왜 틀렸는 지 몰라서 남들이 올려준 반례를 넣어봤다. 틀리다 ㅋ 갈길이 멀다 도대체 알고리즘 공부는 어떻게 하는 지 모르겠다... 학교에서 알분 수업을 들으면 쉬워질까 ? 난 말하는 감자다 그냥 자괴감이 든다. 이 코드를 오늘 새벽에 수정하고 자는게 목표다 근데 그냥 그렇다... 말하는 감자는 자신감이 떨어진다 실버 1문제를 이렇게 오래 고민하나 원래 다 그런가...? 남들은 너무 쉽게 푸는데 나는 너무너무너무 어렵다 다들 처음에는 어려웠겠지? 그치......? ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ 누구한테 물어보고싶다 원래 어려웠죠...? 익숙해지고 많이 푸니까 쉬워지는 거죠 그쵸...?🥺

from collections import deque

queue = deque()

n = int(input())

graph = []
num = [] #각 단지의 수를 위한 배열
count = 0 #각단지수를 더하기 위한 변수
result = 0 #총단지수

for _ in range(n):
    graph.append(list(map(int,input())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue.append((x,y))
    if graph[x][y] == 1:
        while queue:
            x,y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx<=-1 or nx >=n or ny<=-1 or ny>=n: #범위 나가면 검사안하기
                    continue
                if graph[nx][ny] == 0:
                    continue
                if graph[nx][ny] == 1:
                    global count
                    count += 1
                    queue.append((nx,ny))
                    graph[nx][ny] = 0 #방문처리해주기
        return True
    return False

for i in range(n):
    for j in range(n):
        if bfs(i,j) == True:
            result += 1
            num.append(count) #단지수를 추가해주기
            count = 0

print(result) #총 단지수 출력
num.sort()
for i in range(len(num)):
    print(num[i])

오늘은 4월 14일 오늘 새벽에 이거 안뜯어 보면 넌 사람이 아님 ! 이미 아닌가 ..? 힝 내 멘탈 힝 🥲