농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

코드

import sys
input=sys.stdin.readline
from collections import deque

n, m=map(int, input().split())
data=[] 
for i in range(n):
    data.append(list(map(int, input().split())))

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

checkidx=[]

def bfs(x, y, checkidx):
    q=deque([(x,y)])
    visited[x][y]=1
    check=[(x, y)]
    while q:
        X, Y= q.popleft()
        for i in range(8):
            nx, ny= X+dx[i], Y+dy[i] 
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if visited[nx][ny]==1:
                continue
            if data[X][Y]<data[nx][ny]:
                return 0
            if data[X][Y]==data[nx][ny]:
                visited[nx][ny]=1
                q.append((nx,ny))
                check.append((nx,ny))
        checkidx+=check 
    return 1

tot=0
for i in range(n):
    for j in range(m):
        if (i, j) not in checkidx:
            visited=[[0]*m for _ in range(n)]
            tot+=bfs(i,j,checkidx)
print(tot)

문제해결

전형적인 그래프 이론 문제이다. BFS/DFS를 모두 활용할 수 있고, N,M의 크기가 크지 않으므로 모든 조건에 대해 DFS를돌려서 해결 할 수 있다.

필자는 BFS를 이용하여 문제를 해결하였다.

 현재 좌표 기준 8방향 좌표의 높이를 탐색하고, 한 번이라도 보다 더 높은 좌표가 발견된다면 해당 탐색은 산봉우리가 아닌 것으로 처리한다. 만일 같은 높이의 좌표가 발견된다면 큐에 넣고 탐색을 이어간다. 탐색 큐를 모두 살펴본 뒤 마지막에 산봉우리인지 아닌지에 대한 check배열을 확인하여 산봉우리의 개수를 추가해주면 된다. 당연하게도 무한루프에 빠질 수 있으니 방문 배열을 만들어 처리해야 한다.

이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.

학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.

이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.

하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.

학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부터 9 사이의 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 100보다 작거나 같다.

출력

첫째 줄에 구하고자 하는 가장 작은 k값을 출력한다.

8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.

출력

첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다.

태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.

이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.

예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다

랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 태수의 새로운 점수가 주어진다. 이때, 태수의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오. 만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다면 -1을 출력한다.

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다.

입력

첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

코드

import sys
input=sys.stdin.readline
from itertools import combinations

n,s=map(int, input().split())
data=list(map(int, input().split()))
cnt=0

for k in range(1,n+1):
    for i in combinations(data, k):
        total=sum(i)
        if total==s:
            cnt+=1
        
print(cnt)

문제해결

from itertools import combination을 활용하면 편리하다.

파이썬의 내장함수 조합을 활용하면 모든 조건을 탐색하여 해당 조건을 만족하는 결과를 출력할 수 있다.