👩‍🎓공부 - 2023.12.26 오늘의 백준 문제풀이

1926번 - 그림

1로 구별된 그림의 개수와 그림의 넓이를 구하는 문제입니다.
BFS를 활용하면 풀어낼 수 있습니다.

N,M = map(int,input().split())
graph = []
que = deque()
for _ in range(N):
    graph.append(list(map(int,input().split())))

먼저 가로 세로와 BFS 사용을 위한 큐 선언 및 그래프의 크기 등을 받아내겠습니다.

ans_1,ans_2 = 0,0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            a,b = bfs(i,j)
            ans_1 += a
            if b>ans_2:
                ans_2 = b

정답을 받을 변수 1,2를 선언하고 bfs를 돌려 변수1은 그림의 개수이므로 덧셈방식으로, 변수2는 그림의 최대 크기를 담아낼 것이므로 max함수를 지정하는 형식으로 받아줍시다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs(x,y):
    max_draw = 0
    sum = 0
    boolean = False
    que.append([x,y])
    while que:

큐를 선언하고 BFS함수를 작성합니다.

        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 

상하좌우 4방향 탐색을 실시해주고

            if graph[nx][ny] == 1:
                max_draw += 1
                que.append([nx,ny])
                graph[nx][ny] = 2
                boolean = True

1이 존재한다면 그림이 있다는 것이므로 2로 바꿔주고 다음 탐색 후보에 추가해줍시다. boolean같은 경우는 탐색을 했는지 안했는지 구분하기 위해서 작성했씁니다.

    sum += 1
    if boolean == False:
        max_draw += 1
    return sum,max_draw

모든 탐색이 끝났으면 그 주변 그림은 다 탐색한 것이므로 sum값을 1 높여주고 boolean이 탐색을 한번도 한적이 없는 False값이라면 그림이 딱 하나만 존재하므로 max_draw에 1을 더해줍시다.

print(ans_1)
#그림이 하나도 없는 경우
if ans_1 == 0:
    print(0)
else:
    print(ans_2)

마지막으로 그림이 하나도 없는 경우를 고려해서 출력하면 정상적으로 답을 도출해낼 수 있습니다.

1743번 - 음식물 피하기

비슷한 유형의 문제입니다.
그래프가 주어지면 음식물이 가장 많이 뭉쳐있는 부위에 음식물이 몇개나 있는지 구하는 문제입니다.

N,M,K = map(int,input().split())
graph = [[0]*M for _ in range(N)]
visited = [[0]*M for _ in range(N)]
que = deque()
for _ in range(K):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1

BFS조사를 위해서 그래프와 방문여부 등을 선언해주겠습니다.

max = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            a = bfs(i,j)
            if max < a:
                max = a

그래프를 다 살펴봐서 만약 해당 자리에 음식물이 존재한다면 BFS 탐색을 돌려줄겁니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs(x,y):
    sum = 0
    visited[x][y] = 1
    que.append([x,y])

방문했다고 기재해주고 que를 하나 뽑아서 탐색을 시작하겠습니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue

4방향 탐색을 돌리고

            if graph[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = 1
                sum += 1
                que.append([nx,ny])

방문안했고 음식물이 있는 부위라면 방문했다고 표기해주고 sum값을 1 높여준 다음 그다음 탐색후보에 올려둡시다.

    return sum

sum값을 return 해주고

print(max+1)

어짜피 첫 조사는 음식물이 있는 경우를 가정했고 방문한곳은 다시 방문을 안하니까 첫 조사 구역+음식물이 가장 많이 뭉쳐있는 곳 탐색 돈 것을 합해주면 답이 나옵니다.