백준 문제 풀이
2504 괄호의 값
문제
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
풀이
문제 풀이를 시작하기 전에 괄호를 계산했을 때의 수학적인 규칙을 찾아봤다. 입력이 올바른 괄호라고 가정했을 때, 바깥쪽에 있는 괄호값 (2 or 3) 은 안쪽에 있는 괄호값들에 영향을 미치게 된다. 위 문제 설명에 나온 예시를 살펴보면 ‘()[[]]’의 괄호값이 2 + 3×3이고, '()'가 감싸고 있으니 2×2 + 2×3×3가 된다. 이 부분을 보고 아래의 문제 해결법을 생각해 냈다.
여는 괄호가 나오는 경우 해당하는 값을 temp라는 변수에 곱해주고 이 과정을 닫는 괄호가 나오기 전까지 반복한다. 짝이 맞는 닫는 괄호가 나오면 temp의 값을 전체 합에 더해주고, temp는 닫는 괄호의 값만큼 나눠준다. 이 과정을 반복하니 문제를 해결할 수 있었다.
코드
L=list(input())
temp=1
sum=0
merge=[]
for i in range(len(L)):
if L[i]=='(':
temp*=2
merge.append('(')
elif L[i]=='[':
temp*=3
merge.append('[')
elif L[i]==')':
if not merge or merge[-1]!='(':
sum=0
break
if L[i-1]=='(':
sum+=temp
temp//=2
merge.pop()
else:
if not merge or merge[-1]!='[':
sum=0
break
if L[i-1]=='[':
sum+=temp
temp//=3
merge.pop()
if merge:print(0)
else:print(sum)17086 아기 상어2
문제
N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.
어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
안전 거리가 가장 큰 칸을 구해보자.
입력
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.
출력
첫째 줄에 안전 거리의 최댓값을 출력한다.
풀이
bfs를 사용하여 상어로부터 가장 먼 거리를 측정하는 문제였다. 대각선 측정도 가능하기 때문에 x,y 이동을 위한 좌료 리스트를 만들 때 상, 하, 좌, 우, 대각선 4방향의 좌표값을 고려하여 리스트를 만들었다. 상어의 위치부터 시작해서 먼 거리를 측정해야 하기 때문에 처음 입력 받을 때 상어의 좌표를 따로 받아뒀다. 상어 좌표가 있는 동안 반복문을 돌렸고, 입력된 공간에서 아직 측정이 되지 않은 값은 상어와의 최단 거리로 값을 교체해줬다. 값이 교체된 좌표는 상어 좌표를 넣어뒀던 리스트에 넣고 위 과정을 반복한다. 교체된 최단 거리 중 최댓값을 출력한다.
코드
from collections import deque
N,M=map(int, input().split())
ocean=[]
shark=deque()
for i in range(N):
ocean.append(list(map(int, input().split())))
for j in range(M):
if ocean[i][j]==1:
shark.append([i,j])
mx=[0,-1,-1,-1,0,1,1,1]
my=[-1,-1,0,1,1,1,0,-1]
count=0
while(shark):
x,y=shark.popleft()
for k in range(8):
nowx=x+mx[k]
nowy=y+my[k]
if 0<=nowx<N and 0<=nowy<M and ocean[nowx][nowy]==0:
shark.append([nowx,nowy])
ocean[nowx][nowy]=ocean[x][y]+1
if ocean[nowx][nowy]>count:
count=ocean[nowx][nowy]
print(count-1)