99클럽 코테 스터디 18일차 TIL (단지번호붙이기 boj 2667)

오늘의 학습 키워드:  탐색, BFS

문제: 단지번호 붙이기

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

 

풀이

그래프를 탐색하면서 bfs를 돌려 같은 단지를 찾아내는 문제이다.

풀이는 그래프를 돌면서 방문한 적이 없는 노드를 찾아 해당 노드를 시작점으로 bfs를 돌리는 방식으로 진행된다.

코드를 조금 나누어 설명한다.

 

1. Graph & visited 정의

그래프의 가로 세로가 모두 N으로 이루어지기 때문에 쉽게 만들어주었다.

graph = []
for _ in range(N):
    graph.append(sys.stdin.readline().strip())
visited = [[0 for _ in range(N)] for _ in range(N)]

 

2. 반복문을 사용해 bfs함수가 있다고 가정하고 결과 모으기

bfs를 미리 정의하지 않고 반복문을 돌면서 시작점을 bfs함수에 넣는 로직을 먼저 생성해 주었다.

결과를 생각하면서 bfs함수에서 어떤 인자를 받아야 하고, 리턴은 어떻게 해야 하는지 생각할 수 있어 미리 진행했다.

answers = []
for row in range(N):
    for j in range(N):
        if graph[row][j] == '1' and visited[row][j]== 0:
            c = bfs(row,j)
            answers.append(c)

 

3. bfs함수 생성

코드가 길어짐에 따라서 bfs 구문을 함수의 형태로 빼내서 작성해 주었다.

이전에 방문한 기록이 있는지, 확인할 다음 노드가 그래프 안에 있는지, 다음 노드의 값이 1인지 확인하고 해당되는 경우에

큐에 다시 넣음과 동시에 count를 세주었다.

def bfs(s_r,s_c):
    q = deque()
    q.append([s_r,s_c])
    visited[s_r][s_c] = 1
    count = 1

    while q:
        r,c = q.popleft()
        dr = [0,0,-1,1]
        dc = [-1,1,0,0]

        for i in range(4):
            nr = r+dr[i]
            nc = c+dc[i]

            if 0<=nr<N and 0<=nc<N and graph[nr][nc] == '1' and visited[nr][nc] == 0:
                count+=1
                q.append([nr,nc])
                visited[nr][nc] = 1
    return count

 

전체 코드 및 주의사항

문제의 조건의 마지막에 오름차순으로 결괏값을 출력해야 한다는 문장이 있다. 주의

import sys
from collections import deque

N = int(sys.stdin.readline().strip())

graph = []
for _ in range(N):
    graph.append(sys.stdin.readline().strip())
visited = [[0 for _ in range(N)] for _ in range(N)]


def bfs(s_r,s_c):
    q = deque()
    q.append([s_r,s_c])
    visited[s_r][s_c] = 1
    count = 1

    while q:
        r,c = q.popleft()
        dr = [0,0,-1,1]
        dc = [-1,1,0,0]

        for i in range(4):
            nr = r+dr[i]
            nc = c+dc[i]

            if 0<=nr<N and 0<=nc<N and graph[nr][nc] == '1' and visited[nr][nc] == 0:
                count+=1
                q.append([nr,nc])
                visited[nr][nc] = 1
    return count

answers = []
for row in range(N):
    for j in range(N):
        if graph[row][j] == '1' and visited[row][j]== 0:
            c = bfs(row,j)
            answers.append(c)
# print answer
print(len(answers))
answers.sort()
for a in answers:
    print(a)

 

회고

조금씩 감을 찾아가는 기분입니다.

내일 학습할 것.

SQL, Python, 독서