주사위 굴리기
- 난이도 : 골드 3
시키는 대로 구현하면 되는 문제다.(사실 삼성 문제가 다 그렇긴 한데, 시키는 게 어려운걸 시켜서 문제..)
구현 문제일 수록 작업을 나눠서 진행하는 것이 좋다고 생각한다. 그래서 문제를 읽고 작업을 나누는 연습을 계속 진행하고 있다.
이번 문제의 경우는 작업을 어떻게 나눴냐면
- 주사위가 굴러가는 함수 구현(상,하,좌,우)
- 주사위가 도착한 칸에 대한 점수 획득(이때 점수는 BFS로 갈 수 있는 모든 방향 탐색)
- 다음 이동 방향을 결정한다.
지도의 크기는 최대 400이고(20 * 20), 이동 횟수는 1000이기 때문에 시간복잡도는 문제가 없을 것이라 생각하고 편하게 구현하였다.
이 문제에서 가장 어려운 포인트는 1번하고 2번 이었는데, 1번의 경우는 종이에 써가면서 어느 방향으로 구를 때 좌표가 어떻게 변하는지 구하고, 이걸 다 바꿔주는 방식으로 구했다.
2번은 그냥 덱써서 구했다.(근데 풀면 풀수록 덱이 필요가 없는 것 같다. 기본 리스트의 pop(0)을 애용해야할 것 같다)
주사위 굴리는 함수
# 주사위 움직이기
def move_right(c):
case1, case2, case3, case4 = c[1][0], c[1][1], c[1][2], c[3][1]
c[1][1] = case1
c[1][2] = case2
c[3][1] = case3
c[1][0] = case4
def move_left(c):
case1, case2, case3, case4 = c[1][0], c[1][1], c[1][2], c[3][1]
c[1][0] = case2
c[1][1] = case3
c[3][1] = case1
c[1][2] = case4
def move_up(c):
case1, case2, case3, case4 = c[0][1], c[1][1], c[2][1], c[3][1]
c[0][1] = case2
c[1][1] = case3
c[2][1] = case4
c[3][1] = case1
def move_down(c):
case1, case2, case3, case4 = c[0][1], c[1][1], c[2][1], c[3][1]
c[1][1], c[2][1], c[3][1] = case1, case2, case3
c[0][1] = case4
# 아랫면 좌표 : c[3][1]이런식으로 하면 아랫면 좌표가 정확히 c[3][1]에 위치하게 된다.
점수 획득
def calc(x, y, b):
isvisited = [[False] * M for _ in range(N)]
q = deque()
q.append([y, x])
count = 1
while q:
now_y, now_x = q.popleft()
isvisited[now_y][now_x] = True
for i in range(4):
ny = now_y + delta[i][0]
nx = now_x + delta[i][1]
if not check(nx, ny): # 칸을 벗어나면
continue
if isvisited[ny][nx]:
continue
if graph[ny][nx] == b:
q.append([ny, nx])
isvisited[ny][nx] = True
count += 1
return count * b간단한 bfs로, 방문 여부만 조심해서 따져주면 된다.
전체 코드
from collections import deque
# (1,1) -> (N,M)
# N이 세로, M이 가로
N, M, K = map(int, input().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().split())))
# 지도 입력 끝
# 0~N-1 , 0~M-1
# 맵 안에 들어오는지
def check(nextx, nexty):
if 0 <= nextx < M and 0 <= nexty < N:
return True
return False
# 4 * 3 주사위
cube = [[0] * 3 for _ in range(4)]
cube[0][1] = 2
cube[1][0], cube[1][1], cube[1][2] = 4, 1, 3
cube[2][1] = 5
cube[3][1] = 6
# 주사위 움직이기
def move_right(c):
case1, case2, case3, case4 = c[1][0], c[1][1], c[1][2], c[3][1]
c[1][1] = case1
c[1][2] = case2
c[3][1] = case3
c[1][0] = case4
def move_left(c):
case1, case2, case3, case4 = c[1][0], c[1][1], c[1][2], c[3][1]
c[1][0] = case2
c[1][1] = case3
c[3][1] = case1
c[1][2] = case4
def move_up(c):
case1, case2, case3, case4 = c[0][1], c[1][1], c[2][1], c[3][1]
c[0][1] = case2
c[1][1] = case3
c[2][1] = case4
c[3][1] = case1
def move_down(c):
case1, case2, case3, case4 = c[0][1], c[1][1], c[2][1], c[3][1]
c[1][1], c[2][1], c[3][1] = case1, case2, case3
c[0][1] = case4
# 아랫면 좌표 : c[3][1]
direction = 0 # 0 : 동 1 : 남 2 : 서 3 : 븍
# 1. 이동방향으로 한 칸 굴러간다.
def change_dir(y, x):
global direction
ny = y + delta[direction][0]
nx = x + delta[direction][1]
if not check(nx, ny): # 해당 방향에 칸이 없으면 반대 방향으로 바꾼다.
direction += 2
if direction >= 4:
direction -= 4
elif direction < 0:
direction += 4
def move(direct):
global cube
global cube_y
global cube_x
if direct == 0:
move_right(cube)
cube_x += 1
elif direct == 1:
move_down(cube)
cube_y += 1
elif direct == 2:
move_left(cube)
cube_x -= 1
elif direct == 3:
move_up(cube)
cube_y -= 1
delta = [[0, 1], [1, 0], [0, -1], [-1, 0]] # y,x 이동
# 2. 점수 획득
def calc(x, y, b):
isvisited = [[False] * M for _ in range(N)]
q = deque()
q.append([y, x])
count = 1
while q:
now_y, now_x = q.popleft()
isvisited[now_y][now_x] = True
for i in range(4):
ny = now_y + delta[i][0]
nx = now_x + delta[i][1]
if not check(nx, ny): # 칸을 벗어나면
continue
if isvisited[ny][nx]:
continue
if graph[ny][nx] == b:
q.append([ny, nx])
isvisited[ny][nx] = True
count += 1
return count * b
answer = 0
cube_y = 0
cube_x = 0
for _ in range(K):
change_dir(cube_y, cube_x)
move(direction)
B = graph[cube_y][cube_x]
answer += calc(cube_x, cube_y, B)
if cube[3][1] > B:
direction += 1
elif cube[3][1] < B:
direction -= 1
if direction >= 4:
direction -= 4
elif direction < 0:
direction += 4
print(answer)아마 뒤에 문제를 보니까, 이번 시험은 1솔 컷이었을 것 같다.
온풍기 안녕
- 난이도 : 플레 5
나를 6시간이나 고생시켰던 문제..
이 문제의 프로세스는 다음과 같다.
- 집에 있는 모든 온풍기에서 바람이 한 번씩 나온다
- 온도가 조절된다.(문제에 조절 방식이 써있다.)
- 가장 바깥쪽 칸의 온도가 1이상이면, 1감소한다.
- 처음에 주어졌던 조사해야 하는 칸의 온도가 모두 K 이상이면, 테스트를 중단한다.
- 만약 테스트 횟수가 100번을 넘어가면, 101을 출력한다.
프로세스를 봤을 때 정말 어려웠던건 단 하나, 1번이다.
왜냐하면 온풍기 방향이 상,하,좌,우 로 4개 에다가 이번 문제는 그래프가 정사각형이 아닌 직사각형이라 신경을 두배로 써줘야하고, 바람 나오는 조건 중에 벽을 따져야 하는게 정말 까다로웠다. 아마 벽이 없었으면 골드 3,4문제 정도 였을 것 같다.
온도가 증가할 수 있는 경로는 오른쪽으로 나오는 것을 기준으로 ㄱ을 180도 돌린 것이랑, 옆으로 뒤집은 방향 이다. 만약 온풍기의 방향이 오른쪽이 아닌 다른 방향이면, 이것을 회전 시켜서 생각해야 한다.
이것이 문제의 키포인트.
처음에 분명히 테케도 다 맞았는데, 혼자서 다른 테케도 적용해보았는데 문제를 내자마자 틀렸다고 나온 것을 보면, 아마도 벽 조건을 잘못 따진 것 같다.
바람이 퍼지는 방법을 두가지로 구현할 수 있는데,
- for 문을 이용하여 수식 처럼 구현
- queue를 이용
나같은 경우는 1번으로 구현했다가 코드가 300줄 가까이 됐다. 그리고 틀렸다. 조건문이 많아지기 때문에 이 방법은 좋지 않은 것 같고, 2번이 훨씬 좋은 방법인 것 같다.
그래서 2번으로 풀었는데 스트레이트로 풀었는데도 거의 2시간 가까이 걸렸다.
아마 시험장에서 나왔으면 못 풀었을 것 같은 문제다.
온풍기 바람 나오는 함수
회전 시켜서 구하는 게 훨씬 좋을 것 같지만, 나는 회전하면 너무 헷갈릴 것 같아서 그냥 손수 작업해주었다.(어차피 크게 코드가 바뀌지 않기 때문에 상관 없다.)
# [start_x][start_y] : 온풍기가 놓여 있는 장소
def right(start_x, start_y):
global room
q = [[start_x, start_y + 1, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x,y,t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
# 바로 오른쪽
if check(x,y+1) and 1 not in wall[x][y]:
q.append([x,y+1,t-1])
# 위에 오른쪽
if check(x-1,y+1):
if 0 not in wall[x][y] and 1 not in wall[x-1][y]:
q.append([x-1,y+1,t-1])
# 아래 오른쪽
if check(x+1,y+1):
if 0 not in wall[x+1][y] and 1 not in wall[x+1][y]:
q.append([x+1,y+1,t-1])
def left(start_x, start_y):
global room
q = [[start_x, start_y - 1, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x, y, t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
if check(x,y-1): # 바로 왼쪽
if 1 not in wall[x][y-1]:
q.append([x,y-1,t-1])
if check(x-1,y-1): # 왼쪽 위에
if 0 not in wall[x][y] and 1 not in wall[x-1][y-1]:
q.append([x-1,y-1,t-1])
if check(x+1,y-1): # 왼쪽 아래
if not 0 in wall[x+1][y] and 1 not in wall[x+1][y-1]:
q.append([x+1,y-1,t-1])
def up(start_x, start_y):
global room
q = [[start_x -1, start_y, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x, y, t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t == 1:
continue
# 바로 위에
if check(x-1,y):
if 0 not in wall[x][y]:
q.append([x-1,y,t-1])
# 위에 왼쪽
if check(x-1,y-1):
if 0 not in wall[x][y-1] and 1 not in wall[x][y-1]:
q.append([x-1,y-1,t-1])
# 위에 오른쪽
if check(x-1,y+1):
if 0 not in wall[x][y+1] and 1 not in wall[x][y]:
q.append([x-1,y+1,t-1])
def down(start_x, start_y):
global room
q = [[start_x + 1, start_y, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x,y,t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
# 바로 아래쪽
if check(x+1,y):
if 0 not in wall[x+1][y]:
q.append([x+1,y,t-1])
# 아래 왼쪽
if check(x+1,y-1):
if 1 not in wall[x][y-1] and 0 not in wall[x+1][y-1]:
q.append([x+1,y-1,t-1])
# 아래 오른쪽
if check(x+1,y+1):
if 1 not in wall[x][y] and 0 not in wall[x+1][y+1]:
q.append([x+1,y+1,t-1])온도 조절
온도 번져 나가는 것이랑, 바깥쪽 온도 감소하는 것을 한 함수에서 같이 처리해 주었다.
def adjust():
global R,C
delta = [[-1,0],[1,0],[0,1],[0,-1]] # 위 아 오 왼
adjust_list = []
for xx in range(R):
for yy in range(C):
for d in range(len(delta)):
nx = xx + delta[d][0]
ny = yy + delta[d][1]
if not check(nx,ny):
continue
sub = (room[xx][yy] - room[nx][ny]) // 4
if d == 0 and 0 in wall[xx][yy]:
continue
if d == 1 and 0 in wall[nx][ny]:
continue
if d == 2 and 1 in wall[xx][yy]:
continue
if d == 3 and 1 in wall[nx][ny]:
continue
if sub > 0:
adjust_list.append([xx,yy,-sub])
adjust_list.append([nx,ny,sub])
while adjust_list:
x,y,s = adjust_list.pop()
room[x][y] += s
for xx in range(R):
if room[xx][0] > 0:
room[xx][0] -= 1
if room[xx][C-1] > 0:
room[xx][C-1] -= 1
for yy in range(1,C-1):
if room[0][yy] > 0:
room[0][yy] -= 1
if room[R-1][yy] > 0:
room[R-1][yy] -= 1그래서 마지막에 조사를 했을 때 조사하는 모든 칸의 온도가 K이상이거나, 답이 100을 넘어가면 While문을 벗어나는 식으로 구현했다.
전체 코드
room = [] # 방 정보
R,C,K = map(int,input().split())
for _ in range(R):
room.append(list(map(int,input().split())))
W = int(input())
room_wall = [] # 벽 정보
for _ in range(W):
room_wall.append(list(map(int,input().split())))
wall = [[[] for _ in range(C)] for _ in range(R)]
for x,y,t in room_wall:
wall[x-1][y-1].append(t)
### 벽은 (x,y), (x-1,y) 사이 가로벽, (x,y), (x,y+1) 사이 세로벽을 x,y 기준으로 세워진다.
machines = [] # 온풍기 들어 있는 칸
target = [] # 온도 조사해야 하는칸
for i in range(R):
for j in range(C):
if room[i][j] == 5:
target.append([i,j])
elif room[i][j] != 0:
machines.append([i,j,room[i][j]])
room[i][j] = 0
# --- 입력 끝 ---
# 크게 나눠보면
# 1. 온풍기에서 바람 나오는 함수
# 2. 온도 조절
# 3. 바깥쪽 칸 온도 감소
def check(x,y):
if 0<=x<R and 0<=y<C:
return True
return False
# [start_x][start_y] : 온풍기가 놓여 있는 장소
def right(start_x, start_y):
global room
q = [[start_x, start_y + 1, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x,y,t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
# 바로 오른쪽
if check(x,y+1) and 1 not in wall[x][y]:
q.append([x,y+1,t-1])
# 위에 오른쪽
if check(x-1,y+1):
if 0 not in wall[x][y] and 1 not in wall[x-1][y]:
q.append([x-1,y+1,t-1])
# 아래 오른쪽
if check(x+1,y+1):
if 0 not in wall[x+1][y] and 1 not in wall[x+1][y]:
q.append([x+1,y+1,t-1])
def left(start_x, start_y):
global room
q = [[start_x, start_y - 1, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x, y, t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
if check(x,y-1): # 바로 왼쪽
if 1 not in wall[x][y-1]:
q.append([x,y-1,t-1])
if check(x-1,y-1): # 왼쪽 위에
if 0 not in wall[x][y] and 1 not in wall[x-1][y-1]:
q.append([x-1,y-1,t-1])
if check(x+1,y-1): # 왼쪽 아래
if not 0 in wall[x+1][y] and 1 not in wall[x+1][y-1]:
q.append([x+1,y-1,t-1])
def up(start_x, start_y):
global room
q = [[start_x -1, start_y, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x, y, t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t == 1:
continue
# 바로 위에
if check(x-1,y):
if 0 not in wall[x][y]:
q.append([x-1,y,t-1])
# 위에 왼쪽
if check(x-1,y-1):
if 0 not in wall[x][y-1] and 1 not in wall[x][y-1]:
q.append([x-1,y-1,t-1])
# 위에 오른쪽
if check(x-1,y+1):
if 0 not in wall[x][y+1] and 1 not in wall[x][y]:
q.append([x-1,y+1,t-1])
def down(start_x, start_y):
global room
q = [[start_x + 1, start_y, 5]]
isvisited = [[False] * C for _ in range(R)]
while q:
x,y,t = q.pop(0)
if isvisited[x][y]:
continue
isvisited[x][y] = True
room[x][y] += t
if t <= 1:
continue
# 바로 아래쪽
if check(x+1,y):
if 0 not in wall[x+1][y]:
q.append([x+1,y,t-1])
# 아래 왼쪽
if check(x+1,y-1):
if 1 not in wall[x][y-1] and 0 not in wall[x+1][y-1]:
q.append([x+1,y-1,t-1])
# 아래 오른쪽
if check(x+1,y+1):
if 1 not in wall[x][y] and 0 not in wall[x+1][y+1]:
q.append([x+1,y+1,t-1])
def adjust():
global R,C
delta = [[-1,0],[1,0],[0,1],[0,-1]] # 위 아 오 왼
adjust_list = []
for xx in range(R):
for yy in range(C):
for d in range(len(delta)):
nx = xx + delta[d][0]
ny = yy + delta[d][1]
if not check(nx,ny):
continue
sub = (room[xx][yy] - room[nx][ny]) // 4
if d == 0 and 0 in wall[xx][yy]:
continue
if d == 1 and 0 in wall[nx][ny]:
continue
if d == 2 and 1 in wall[xx][yy]:
continue
if d == 3 and 1 in wall[nx][ny]:
continue
if sub > 0:
adjust_list.append([xx,yy,-sub])
adjust_list.append([nx,ny,sub])
while adjust_list:
x,y,s = adjust_list.pop()
room[x][y] += s
for xx in range(R):
if room[xx][0] > 0:
room[xx][0] -= 1
if room[xx][C-1] > 0:
room[xx][C-1] -= 1
for yy in range(1,C-1):
if room[0][yy] > 0:
room[0][yy] -= 1
if room[R-1][yy] > 0:
room[R-1][yy] -= 1
def survey():
global target
global K
global room
for x,y in target:
if room[x][y] < K:
return False
return True
answer = 0
while True:
answer += 1
for init_x, init_y, d in machines:
if d == 1:
right(init_x,init_y)
elif d == 2:
left(init_x, init_y)
elif d == 3:
up(init_x, init_y)
elif d == 4:
down(init_x,init_y)
adjust()
if survey():
break
if answer > 100:
answer = 101
break
if answer > 100:
answer = 101
print(answer)
2021년 하반기 문제 복기 끝!
Hongik CE