큰 제약사항이나 알고리즘이 따로 사용되지는 않으므로 순서에 맞게 그대로 구현만 잘 해주면 된다.
풀이 과정
문제에서 특별히 신경써주어야 하는 부분은, 조건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)
연구소의 각 칸은 0, 1, 2로 구성되어 있으며 0은 빈 칸, 1은 벽, 2은 바이러스 이다.
바이러스는 벽을 뚫고 확장할 수 없으며 상하좌우에 인접한 빈 칸으로만 확장이 가능하다.
위 그림과 같이 N x M 모양의 연구소(행렬)가 주어지며, 3개의 벽(1)을 세워야 한다.
3개의 벽을 세웠을 때, 안전영역의 크기(0의 개수)의 최댓값을 구하면 된다.
풀이 과정
바이러스는 '2' 이며 상하좌우의 인접한 빈칸(0)으로만 이동이 가능하기 때문에
먼저 '2'인 칸들을 모두 큐에 넣어준 후에,
BFS(너비우선탐색)을 통해 큐에서 하나씩 꺼내 확장시키는 방식으로 진행하면 된다.
2인 칸에서 시작하여 주변의 0인 칸들을 2로 만드는 방식이다.
이 때, 어디에 벽을 세워야 최댓값이 나올지는 알 수 없기 때문에 벽을 세울 수 있는 모든 경우의 수에 대해 수행해봐야 한다.
따라서, (1, 1) 칸 부터 (n, m)칸 까지 중 빈칸을 순서대로 하나씩 3개 선택하여
벽을 세우고 BFS를 수행한 후 벽을 지우고
그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야 한다.
즉, 백트래킹방식을 이용해 3개의 벽을 모든 칸에 세워본다.
이렇게 진행하면서 최댓값을 저장한 후, 모든 탐색이 끝난 후 최댓값을 출력하면 된다.
이를 파이썬으로 나타낸 코드는 다음과 같다.
from collections import deque
import copy
def bfs():
queue = deque()
tmp_graph = copy.deepcopy(graph)
for i in range(n):
for j in range(m):
if tmp_graph[i][j] == 2:
queue.append((i, j))
while queue:
x, y = queue.popleft()
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:
continue
if tmp_graph[nx][ny] == 0:
tmp_graph[nx][ny] = 2
queue.append((nx, ny))
global answer
cnt = 0
for i in range(n):
cnt += tmp_graph[i].count(0)
answer = max(answer, cnt)
def makeWall(cnt):
if cnt == 3:
bfs()
return
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
graph[i][j] = 1
makeWall(cnt+1)
graph[i][j] = 0
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
answer = 0
makeWall(0)
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])
④ 뱀이 이동할 때 마다 머리와 꼬리는 한 칸씩 전진한다. (즉, 몸의 길이는 그대로이다.)
⑤ 이동했을 때 사과를 먹으면 머리는 전진하지만 꼬리는 그대로이다. (즉, 몸의 길이가 한 칸 늘어난다.)
⑥ 방향 전환을 해야 하는 타이밍에 맞춰 L이면 왼쪽, D이면 오른쪽으로 방향전환을 한다.
이렇게 무엇을 구현해야 할 지를 정리한 후에 이를 하나씩 차례차례 구현해주면 된다.
①②③ 은 그대로 구현을 하면 되기 때문에 따로 설명은 하지 않고
④의 경우에는 처음 시작 할 때, [0, 0]을 큐에 넣어 몸길이 1 뱀의 초기 위치 상태를 저장하고,
오른쪽으로 한 칸 이동하여 [0, 0]을 큐에서 pop하고
[0, 1]을 큐에 push하여 뱀의 위치 상태를 변경한다.
이런 식으로 뱀을 전진시키면 된다. ( 큐를 뱀의 몸을 나타낸다고 생각하면 된다. )
⑤의 경우는 graph[x][y] = 2일 때 이다. 머리만 전진하면 되므로 큐에서 pop을 하지 않고,
큐에 현재 머리 위치만 push함으로써 뱀의 몸 길이를 늘려준다.
⑥의 경우에는 현재 시간이 방향전환을 해야 하는 시간이면, 입력한 방향에 맞게 전환을 해주면 된다.
(딕셔너리를 이용해 시간을 키값으로, 방향을 밸류값으로 입력받았다.)
이를 코드로 나타내면 다음과 같다.
from collections import deque
n = int(input())
k = int(input())
graph = [[0] * n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(k):
a, b = map(int, input().split())
graph[a - 1][b - 1] = 2
l = int(input())
dirDict = dict()
queue = deque()
queue.append((0, 0))
for i in range(l):
x, c = input().split()
dirDict[int(x)] = c
x, y = 0, 0
graph[x][y] = 1
cnt = 0
direction = 0
def turn(alpha):
global direction
if alpha == 'L':
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
while True:
cnt += 1
x += dx[direction]
y += dy[direction]
if x < 0 or x >= n or y < 0 or y >= n:
break
if graph[x][y] == 2:
graph[x][y] = 1
queue.append((x, y))
if cnt in dirDict:
turn(dirDict[cnt])
elif graph[x][y] == 0:
graph[x][y] = 1
queue.append((x, y))
tx, ty = queue.popleft()
graph[tx][ty] = 0
if cnt in dirDict:
turn(dirDict[cnt])
else:
break
print(cnt)
만약, 동쪽으로 움직인다면 모든 행에 대해 n - 1칸부터 0번째 칸까지 동쪽으로 움직이는 것을 구현한다.
현재 움직이려는 블록의 동쪽 마지노선의 블록이 현재 블록과 같은 수라면
수를 더해준 후 마지노선 칸에 그 수를 넣어주고
현재 블록은 0으로 만들어 다음 블록들이 이동할 수 있도록 만든다.
( 0 0 2 2 = > 0 0 0 4 )
마지노선 블록이 0이라면 그 칸을 현재 블록의 숫자로 대체한 후
현재 블록을 0으로 만든다.
마지노선이 현재 블록과 같은 수가 아니라면, 합칠 수가 없기 때문에 마지노선을 하나 당긴다.
여기서 말하는 마지노선이란, 처음에는 동쪽 가장 끝이 될 것이며
동쪽 가장 끝이 이미 계산이 된 상태라면 -1씩 해주어 마지노선을 하나씩 줄여주는 것을 말한다.
그리고, 동쪽으로 움직인 경우를 만든 후에
서쪽으로 움직일 때는 동쪽으로 움직인 게임판을 이어서 이용하는 것이 아니라
동쪽으로 움직이기 전의 게임판을 서쪽으로 움직여야 하기 때문에
깊은복사(DeepCopy)를 통해 기존 맵을 복사해둔 후에 그 맵을 이동하도록 한다.
이를 코드로 구현하면 다음과 같다.
from copy import deepcopy
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
def move(board, dir):
if dir == 0: # 동쪽
for i in range(n):
top = n - 1
for j in range(n - 2, -1, -1):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[i][top] == 0:
board[i][top] = tmp
elif board[i][top] == tmp:
board[i][top] = tmp * 2
top -= 1
else:
top -= 1
board[i][top] = tmp
elif dir == 1: # 서쪽
for i in range(n):
top = 0
for j in range(1, n):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[i][top] == 0:
board[i][top] = tmp
elif board[i][top] == tmp:
board[i][top] = tmp * 2
top += 1
else:
top += 1
board[i][top] = tmp
elif dir == 2: # 남쪽
for j in range(n):
top = n - 1
for i in range(n - 2, -1, -1):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[top][j] == 0:
board[top][j] = tmp
elif board[top][j] == tmp:
board[top][j] = tmp * 2
top -= 1
else:
top -= 1
board[top][j] = tmp
else:
for j in range(n):
top = 0
for i in range(1, n):
if board[i][j]:
tmp = board[i][j]
board[i][j] = 0
if board[top][j] == 0:
board[top][j] = tmp
elif board[top][j] == tmp:
board[top][j] = tmp * 2
top += 1
else:
top += 1
board[top][j] = tmp
return board
def dfs(board, cnt):
global ans
if cnt == 5:
for i in range(n):
for j in range(n):
ans = max(ans, board[i][j])
return
for i in range(4):
tmp_board = move(deepcopy(board), i)
dfs(tmp_board, cnt + 1)
ans = 0
dfs(graph, 0)
print(ans)
