큰 제약사항이나 알고리즘이 따로 사용되지는 않으므로 순서에 맞게 그대로 구현만 잘 해주면 된다.
풀이 과정
문제에서 특별히 신경써주어야 하는 부분은, 조건5 부분이다.
먼저, 구름이 di 방향으로 si칸 이동한 후에 비를 뿌리고 구름은 사라진다.
이 때, 구름이 사라진 칸은 물복사 버그 후에 구름이 생길 수 없기 때문에 1로 표시해주어
해당 턴에 구름이 생길 수 없도록 해주었다.
그리고 그 칸에 영원히 구름이 생길 수 없는 것이 아니라,
해당 턴에만 생길 수 없기 때문에
raining 함수의 마지막 부분에 1로 표시해둔 칸을 다시 0으로 표시하여 구름이 생길 수 있도록 해주었다.
코드의 cloud는 현재 턴에서 처음의 구름 위치를 담은 큐이고
queue는 이 구름들을 이동시킨 후의 구름 위치이다.
from collections import deque
n, m = map(int, input().split())
board = []
rain = [[0] * n for _ in range(n)]
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
for i in range(n):
board.append(list(map(int, input().split())))
cloud = deque([(n - 1, 0), (n - 1, 1), (n - 2, 0), (n - 2, 1)])
def raining(dir, dist):
queue = deque()
while cloud:
a, b = cloud.popleft()
nx = (a + dx[dir] * dist) % n
ny = (b + dy[dir] * dist) % n
board[nx][ny] += 1
rain[nx][ny] = 1 # 사라진 칸은 1 표시
queue.append((nx, ny))
while queue:
a, b = queue.popleft()
for i in range(1, 8, 2):
nx = a + dx[i]
ny = b + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] > 0:
board[a][b] += 1
for i in range(n):
for j in range(n):
if rain[i][j] == 1:
rain[i][j] = 0
continue
if board[i][j] >= 2:
cloud.append((i, j))
board[i][j] -= 2
for i in range(m):
d, s = map(int, input().split())
raining(d - 1, s)
answer = 0
for i in range(n):
answer += sum(board[i])
print(answer)
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
풀이 과정
이 문제는 푸는 방법이 다양하다.
DFS를 이용해 푸는 방법도 있고, 직접 테트리스 모형을 모두 고려하여 하나하나 확인해주는 방법도 있다.
DFS를 이용한 풀이는 깔끔하다는 장점이 있지만 시간이 좀 더 오래걸린다는 단점이 있고
직접 테트리스 모형을 만드는 풀이는 시간이 빠르다는 장점이 있지만, 구현이 조금 지저분하다는 단점이 있다.
시간을 고려한다면 직접 만드는 풀이가 좋을 것이며,
깔끔한 풀이를 고려한다면 DFS 풀이가 좋을 것 같다.
그래서 두 방법 모두 풀어보았다.
① 먼저 DFS를 이용한 풀이는 백트래킹을 이용해 맵의 처음부터 끝칸까지 모든 칸에 대해 DFS를 수행한다.
한 칸에서 DFS를 수행하게 되면 모든 테트리스 모형을 확인할 수가 있다.
예를 들어, 쭉 오른쪽으로 간다면 ㅡ 모양이 될 것이고
오른쪽으로 갔다 아래로 갔다 왼쪽으로 가면 ㅁ 모양이 완성될 것이다.
하지만 ㅗ 모양이 DFS로 완성할 수 없기 때문에
depth = 1일 때, 즉 2칸까지 완성했을 때 칸을 다음칸으로 옮기지 않은 그대로인 상태에서
DFS를 수행함으로써 ㅗ 모양을 만들 수 있다.
1번 풀이를 이용한 코드는 다음과 같다.
n, m = map(int, input().split())
board = []
visited = [[False] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
board.append(list(map(int, input().split())))
answer = 0
def dfs(x, y, mysum, depth):
global answer
if depth == 3:
answer = max(answer, mysum)
return
else:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny]:
continue
if depth == 1: # ㅗ 모양은 DFS로 만들 수 없으므로 예외처리
visited[nx][ny] = True
dfs(x, y, mysum + board[nx][ny], depth + 1)
visited[nx][ny] = False
visited[nx][ny] = True
dfs(nx, ny, mysum + board[nx][ny], depth + 1)
visited[nx][ny] = False
for i in range(n):
for j in range(m):
visited[i][j] = True
dfs(i, j, board[i][j], 0)
visited[i][j] = False
print(answer)
② 테트리스 모형을 모두 배열로 만들어서 비교한다.
첫 칸부터 끝칸까지 모든 칸에 대해 테트리스 모형을 대입하여 최댓값을 비교해나가는 방식이다.
n, m = map(int, input().split())
board = []
for i in range(n):
board.append(list(map(int, input().split())))
tetris = [
[(0, 0), (0, 1), (1, 0), (1, 1)], # ㅡ
[(0, 0), (0, 1), (0, 2), (0, 3)], # ㅣ
[(0, 0), (1, 0), (2, 0), (3, 0)], # ㅁ
[(0, 0), (1, 0), (1, 1), (2, 1)], # h
[(1, 0), (0, 1), (1, 1), (2, 0)], # h 회전
[(1, 0), (1, 1), (0, 1), (0, 2)], # ...
[(0, 0), (0, 1), (1, 1), (1, 2)],
[(0, 0), (1, 0), (2, 0), (2, 1)], # L
[(0, 1), (1, 1), (2, 0), (2, 1)], # ...
[(0, 0), (0, 1), (1, 0), (2, 0)],
[(0, 0), (0, 1), (1, 1), (2, 1)],
[(1, 0), (0, 1), (1, 1), (1, 2)],
[(0, 0), (0, 1), (0, 2), (1, 1)],
[(0, 0), (1, 0), (1, 1), (1, 2)],
[(1, 0), (1, 1), (1, 2), (0, 2)],
[(0, 0), (0, 1), (0, 2), (1, 0)],
[(0, 0), (0, 1), (0, 2), (1, 2)],
[(0, 0), (1, 0), (1, 1), (2, 0)],
[(1, 0), (0, 1), (1, 1), (2, 1)] # ㅓ
]
def solution(x, y):
global answer
for i in range(19):
tmp = 0
for j in range(4):
nx = x + tetris[i][j][0]
ny = y + tetris[i][j][1]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
break
tmp += board[nx][ny]
answer = max(answer, tmp)
answer = 0
for i in range(n):
for j in range(m):
solution(i, j)
print(answer)
③ 마찬가지로 모든 테트리스칸에 대해 수행하는 방법이지만
배열에 모두 기입하는 것이 아닌 함수로 하나씩 만들어 대입하는 방법이다.
수행시간은 이 풀이가 가장 짧았다.
하지만 구현해야 하는 코드의 길이가 상당히 긴 단점이 있다.
n, m = map(int,input().split())
graph = []
ans = 0
def shape1(i, j): # ㅡ
if j+3 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i][j+3]
def shape2(i, j): # ㅣ
if i+3 >= n:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j]
def shape3(i, j): # L모양
if i+2 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1]
def shape4(i, j): # L모양 대칭
if i+2 >= n or j-1 < 0:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j-1]
def shape5(i, j): # L모양 시계방향 회전
if i-1 < 0 or j+2 >= m:
return 0
return graph[i][j] + graph[i-1][j] + graph[i-1][j+1] + graph[i-1][j+2]
def shape6(i, j): # L대칭 시계방향 회전
if i+1 >= n or j+2 >=m:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+1][j+2]
def shape7(i, j): # L 시계방향 회전x2
if i+2 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1]
def shape8(i, j): # L대칭 시계방향 회전x2
if i+2 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+2][j]
def shape9(i, j): # L 시계방향 회전x3
if i-1 < 0 or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i-1][j+2]
def shape10(i, j): # L대칭 시계방향 회전x3
if i+1 >= n or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i+1][j+2]
def shape11(i, j): # ㅁ모양
if i+1 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+1][j+1]
def shape12(i, j): # 번개모양
if i+2 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1]
def shape13(i, j): # 번개모양 회전
if i-1 < 0 or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i-1][j+2]
def shape14(i, j): #번개모양 대칭
if i+2 >= n or j-1 < 0:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j-1]
def shape15(i, j): #번개모양 대칭 회전
if i+1 >= n or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j+2]
def shape16(i, j): #ㅗ모양
if i-1 < 0 or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i][j+2]
def shape17(i, j): #ㅗ모양 회전
if i+2 >= n or j+1 >= m:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j]
def shape18(i, j): #ㅗ모양 회전x2
if i+1 >= n or j+2 >= m:
return 0
return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i][j+2]
def shape19(i, j): #ㅗ모양 회전x3
if i+2 >= n or j-1 < 0:
return 0
return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j]
for i in range(n):
graph.append(list(map(int,input().split())))
for i in range(n):
for j in range(m):
ans = max(ans, shape1(i,j), shape2(i,j), shape3(i,j), shape4(i,j), shape5(i,j), shape6(i,j), shape7(i,j), shape8(i,j), shape9(i,j),
shape10(i,j), shape11(i,j), shape12(i,j), shape13(i,j), shape14(i,j), shape15(i,j), shape16(i,j), shape17(i,j), shape18(i,j), shape19(i,j))
print(ans)
그리고 주사위를 상, 하, 좌, 우 로 굴리게 되는데 주사위와 바닥에 닿는 면은 맵의 숫자로 복사가 된다.
그리고 주사위를 굴렸을 때 주사위 위쪽면의 숫자를 출력해야 한다.
따라서, 주사위 전개도를 생각하며 풀어야 하는 문제이다.
풀이 과정
이 문제를 풀기 위해 주사위 전개도를 직접 그려보면서 생각을 했다.
문제에서 주어진 주사위 전개도를 보면 다음과 같이 생겼는데
주사위 전개도
1을 위쪽으로 6을 아래쪽으로 접게되면 다음과 같은 주사위가 탄생한다.
그리고 이 주사위를 상, 하, 좌, 우로 굴렸을 때의 모양을 생각해야 한다.
대표적으로, 좌 로 굴렸을 때의 주사위는 다음과 같다.
좌로 굴린 주사위
이 때 주사위가 어떻게 변했는지 보자.
인덱스 0부터 5까지 각각의 인덱스가 위쪽, 뒤쪽, 오른쪽, 왼쪽, 앞쪽, 바닥 이라고 했을 때
[1, 2, 3, 4, 5, 6] => [3, 2, 6, 1, 5, 4] 로 변했음을 알 수 있다.
마찬가지로 다른 방향으로 굴렸을 때에 대해서도 어떻게 변했는지를 알면 이 문제를 다 풀었다고 볼 수 있다.
이러한 규칙을 turn함수에 정의를 해놓고
굴려야 하는 타이밍에 함수를 실행시키면 된다.
나머지부분은 문제에서 주어진 대로 구현만 하면 된다.
이를 파이썬으로 나타낸 코드는 다음과 같다.
n, m, x, y, k = map(int, input().split())
board = []
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
dice = [0, 0, 0, 0, 0, 0]
def turn(dir):
a, b, c, d, e, f = dice[0], dice[1], dice[2], dice[3], dice[4], dice[5]
if dir == 1: #동
dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = d, b, a, f, e, c
elif dir == 2: #서
dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = c, b, f, a, e, d
elif dir == 3: #북
dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = e, a, c, d, f, b
else:
dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = b, f, c, d, a, e
for i in range(n):
board.append(list(map(int, input().split())))
comm = list(map(int, input().split()))
nx, ny = x, y
for i in comm:
nx += dx[i-1]
ny += dy[i-1]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
nx -= dx[i-1]
ny -= dy[i-1]
continue
turn(i)
if board[nx][ny] == 0:
board[nx][ny] = dice[-1]
else:
dice[-1] = board[nx][ny]
board[nx][ny] = 0
print(dice[0])
먼저, 좌표 압축이라는 것은 여러 곳에 흩뿌려진 좌표들을 연속된 수들로 모아 압축하는 것을 말한다.
예를 들어, 다음과 같은 좌표가 있다고 하자.
[1, 10, 10000, 1000000]
이렇게 네 점의 좌표가 있을 때, 좌표는 네 개 이지만 좌표값이 1부터 1,000,000 까지 있다.
하지만 이 좌표를 압축하여 순서대로 표현하면 [0, 1, 2, 3] 이 된다.
즉, 작은 값부터 시작해서 0부터 인덱스를 부여하는 방식이다.
1이 가장 작으므로 0이되고 10이 1, 10000이 2, 1000000이 3이 되는 것이다.
좌표압축을 위해 먼저 수들을 입력받은 후에,
정렬을 하기전에 앞서, 같은 수는 같은 좌표값을 가지므로 집합(Set)으로 중복값을 없애주자.
그리고 정렬을 해서 각 숫자들과 인덱스를 딕셔너리에 저장을 하면 된다.
이를 나타낸 파이썬 코드는 다음과 같다.
import sys
n = int(input())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
numset = set(numbers)
a = list(numset)
a.sort()
numdict = {}
for i in range(len(a)):
numdict[a[i]] = i
for i in numbers:
print(numdict[i], end=' ')
두 좌표 (x1, y1)와 (x2, y2)가 주어지고, 목표점과의 거리 r1, r2가 주어질 때
목표점이 존재할 수 있는 좌표의 수를 구하는 문제이다.
풀이 과정
이 문제는 고등학교 교과과정에서 배웠던 원의 방정식 중 두 원의 교점을 활용하는 문제이다.
먼저, 원이라는 것은 하나의 정점으로부터 같은 거리를 가지는 점들의 집합이므로
정점(x1, y1)로 부터 거리 r1을 가진 점들은 원으로 존재할 것이고
정점(x2, y2)로 부터 거리 r2을 가진 점들은 원으로 존재할 것이기 때문이다.
두 원은 다음과 같은 관계로 존재할 수 있다.
출처 : Primitive님 블로그
위의 경우들을 다음과 같이 코드로 표현하면 되는 문제이다.
import math
t = int(input())
for i in range(t):
x1, y1, r1, x2, y2, r2 = map(int, input().split())
dist = math.sqrt((x1 - x2)**2 + (y1-y2)**2)
if x1 == x2 and y1 == y2: # 두 원의 중심이 같을 때
if r1 == r2: # 반지름이 같으면 : 같은 원
print(-1)
else:
print(0) # 다르면 영원히 만나지 않음
else: # 두 원의 중심이 다를 때
if abs(r1-r2) == dist or r1 + r2 == dist: # 내접원 or 외접원
print(1)
elif abs(r1-r2) < dist < r1 + r2: # 두 점에서 만날 때
print(2)
else: # 만나지 않음
print(0)
