[엘리스] 유치원 소풍

유치원 소풍

상훈이는 엘리스 유치원 선생님입니다. 엘리스 유치원 학생들은 다 같이 어은동산으로 소풍을 갔습니다. 그런데 엘리스 유치원 학생들은 서로 파벌이 나뉘어 있어서 절대로 다른 조직과는 점심을 같이 먹지 않습니다. 상훈 선생님은 점심을 먹는 애들을 보면서 어느 조직에 몇명이 있는 지를 알려고 합니다. 여러분은 점심을 먹는 학생들의 지도를 바탕으로 어느 조직에 몇 명이 있는지 알아내면 됩니다.

 

학생들은 다음과 같이 앉아 있습니다.

다음과 같이 파벌이 나뉩니다.

여러분이 출력해야 할 것은 파벌이 몇 개 있는지, 그리고 각 파벌에는 몇 명이 있는 지를 오름차순으로 정리한 결과입니다.

---

입력

첫째 줄에는 지도의 크기가 주어집니다. 지도는 항상 정사각형입니다. 두 번째 줄부터 지도의 정보가 주어집니다. 1은 해당 자리에 학생이 있다는 뜻이고, 0은 없다는 뜻입니다.

출력

첫 번째 줄에는 파벌의 전체 개수를 출력합니다. 두 번째 줄부터 각 파벌에 속한 학생의 수를 오름차순으로 정렬한 결과를 출력합니다.

입력 예시

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

출력 예시

3
7
8
9

풀이

BFS를 이용한 풀이

1. Queue에 시작점을 넣고 위, 아래, 왼쪽, 오른쪽으로 갈 수 있는 경우를 넣어줌
   • 단, 이미 방문한 위치나 길이 없는 곳은 진행하지 않음
2. Queue에서 값 하나를 빼서 거기로 이동
3. 마찬가지로 가능한 경우를 넣어줌
4. 2로 돌아가서 Queue에 있는 값이 모두 빠질때까지 진행

import queue

def isOkay(pMap, y, x):
    n = len(pMap)

    if 0 <= y and y <n and 0 <= x and x < n:
        return True
    else:
        return False

def findStudents(pMap, y, x, visited):
    '''
    pMap의 (y, x)에 있는 학생과 같은 편인 학생의 수를 반환하고, visited에 색칠하는 함수 
    '''

    '''
    BFS로 작성
    1. Queue에다가 시작점을 넣고 BFS 시작 
    2. Queue에서 하나를 뺀다. 이것이 곧 내가 현재 있는 위치
    3. 내 위치에서 인접한 정점 중 방문하지 않은 정점을 모두 Queue에 넣는다. 
    4. 다시 2로 돌아간다 
    '''
    myQueue = queue.Queue()
    myQueue.put((y, x))
    visited[y][x] = True
    numStudents = 0
    while not myQueue.empty() : #큐에 데이터가 없을 때 까지 돌아야 함 
        current = myQueue.get()

        y = current[0]
        x = current[1]
        numStudents += 1

        # isOkay : 좌표가 범위내에 있는지 여부 
        if isOkay(pMap, y-1, x) and pMap[y-1][x] == 1 and visited[y-1][x] == False:
            myQueue.put((y-1, x))
            visited[y-1][x] = True

        if isOkay(pMap, y, x-1) and pMap[y][x-1] == 1 and visited[y][x-1] == False:
            myQueue.put((y, x-1))
            visited[y][x-1] = True

        if isOkay(pMap, y, x+1) and pMap[y][x+1] == 1 and visited[y][x+1] == False:
            myQueue.put((y, x+1))
            visited[y][x+1] = True

        if isOkay(pMap, y+1, x) and pMap[y+1][x] == 1 and visited[y+1][x] == False:
            myQueue.put((y+1, x))
            visited[y+1][x] = True

    return numStudents

def picnic(pMap):
    '''
    유치원의 파벌 개수를 반환하는 함수를 작성하세요.
    '''
    n = len(pMap)
    result = []
    visited = [ [False for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if pMap[i][j] == 1 and visited[i][j] == False:
                numStudents = findStudents(pMap, i, j, visited)
                result.append(numStudents)
    result = sorted(result)
    return (len(result), result)

def read_input():
    size = int(input())
    returnMap = []
    for i in range(size):
        line = input()
        __line = []
        for j in range(len(line)) :
            __line.append(int(line[j]))

        returnMap.append(__line)
    return returnMap

def main():
    pMap = read_input()
    print(picnic(pMap))

if __name__ == "__main__":
    main()

DFS를 이용한 풀이

1. Array에 시작점을 넣고 위, 아래, 왼쪽, 오른쪽순으로 갈 수 있는 곳까지 진행
   • 단, 이미 방문한 위치나 길이 없는 곳은 진행하지 않음
2. 진행할 수 없는 곳에 도착하면, 이전의 위치로 돌아감
3. 2를 반복해서 진행하면서 진행가능한 곳까지 이동함
4. 3을 계속하다가 진행가능한 곳이 없으면 종료

def findStudents(pMap, y, x, visited, cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    for c in range(len(dx)):
        if (y+dy[c] >= 0) & (x+dx[c] >= 0) & (y+dy[c] <= len(pMap)-1) & (x+dx[c] <= len(pMap)-1):
            if (pMap[y+dy[c]][x+dx[c]] == 1) & (visited[y+dy[c]][x+dx[c]] == False):
                visited[y+dy[c]][x+dx[c]] = True
                cnt += 1
                cnt = findStudents(pMap, y+dy[c], x+dx[c], visited, cnt)

    return cnt


def picnic(pMap):
    '''
    유치원의 파벌 개수를 반환하는 함수를 작성하세요.
    '''    
    n = len(pMap)
    result = []
    visited = [[False for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if (pMap[i][j] == 1) & (visited[i][j] == False):
                visited[i][j] = True
                Numbers = findStudents(pMap, i, j, visited, 1)
                result.append(Numbers)
    result = sorted(result)
    return (len(result), result)

def read_input():
    size = int(input())
    returnMap = []
    for i in range(size):
        line = input()
        __line = []
        for j in range(len(line)) :
            __line.append(int(line[j]))

        returnMap.append(__line)
    return returnMap

def main():
    pMap = read_input()
    print(picnic(pMap))

if __name__ == "__main__":
    main()

모범 답안

def picnic(pMap):
    '''
    유치원의 파벌 개수를 반환하는 함수를 작성하세요.
    '''
    n = len(pMap)
    def dfs(i,j,pMap,check,n,cnt) :
        check[i][j] = 1
        dir = [[0,1],[1,0],[0,-1],[-1,0]]
        for y,x in dir :
            if -1<i+y<n and -1<j+x<n and pMap[i+y][j+x] == 1 and check[i+y][j+x] != 1 :
                cnt = dfs(i+y,j+x,pMap,check,n,cnt+1)
        return cnt
    result = []
    check = [[0 for i in range(n)] for j in range(n)]
    for i in range(n) :
        for j in range(n) :
            # print(i,j)
            if pMap[i][j] == 1 and check[i][j] != 1:
                result.append(dfs(i,j,pMap,check,n,1))
    result.sort()
    
    return (len(result),result)

def read_input():
    size = int(input())
    returnMap = []
    for i in range(size):
        line = input()
        __line = []
        for j in range(len(line)) :
            __line.append(int(line[j]))
        
        returnMap.append(__line)
    return returnMap

def main():
    pMap = read_input()
    print(picnic(pMap))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn