백준 15685 드래곤 커브
https://www.acmicpc.net/problem/15685 (opens in a new tab)
내 풀이
from collections import deque
N = int(input())
graph = [[0 for _ in range(200)] for _ in range(200)]
all_edge = deque()
visited = []
move_rule = {
0: [0,1], 1: [-1,0], 2: [0,-1], 3: [1,0]
}
dragon_rule = {
0:1,1:2,2:3,3:0
}
move = []
for _ in range(N):
move = []
x, y, d, g = map(int, input().split())
# 다음 움직일 장소 정렬
cur_move = move_rule[d]
ny, nx = y + cur_move[0], x + cur_move[1]
graph[y][x], graph[ny][nx] = 1, 1
all_edge.append([y,x])
all_edge.append([ny,nx])
last = [ny, nx]
move.append(d)
for _ in range(g) :
tmp = len(move) - 1
for m in range(tmp, -1, -1) :
# 다음 이동 결정
nm = dragon_rule[move[m]]
move.append(nm) # 움직인 방향 추가
cur_move = move_rule[nm]
# 다음 장소로 이동 후 저장
ny, nx = last[0] + cur_move[0], last[1] + cur_move[1]
all_edge.append([ny, nx])
graph[ny][nx] = 1
last = [ny,nx] # 마지막 움직인 곳 변경
cnt = 0
def check(v1, v2, v3, v4) :
global cnt
if graph[v1[0]][v1[1]] and graph[v2[0]][v2[1]] and graph[v3[0]][v3[1]] and graph[v4[0]][v4[1]] :
visit = [v1, v2, v3, v4]
visit.sort()
if not (visit in visited) :
cnt += 1
visited.append(visit)
while all_edge :
y, x = all_edge.popleft()
# 1사분면 확인
check([y,x], [y+1, x], [y+1, x+1], [y,x+1])
# 2사분면 확인
check([y,x], [y-1, x], [y-1, x+1], [y,x+1])
# 3사분면 확인
check([y,x], [y-1, x], [y-1, x-1], [y,x-1])
# 4사분면 확인
check([y,x], [y+1, x], [y+1, x-1], [y,x-1])
print(cnt)첫 번째 개선 버전
모든 edge를 한 번씩 검사한다고 가정했을 때 모든 사분면에 대해서 검사하는게 아니라, 한 개의 사분면만 검사하면 되지 않을까? 라는 생각에 all_edge를 중복검사를 하고 1사분면이 정사각형이 성립하는지만 검사하는 코드이다.
실행속도가 1532ms에서 348ms로 크게 개선되었다.
from collections import deque
N = int(input())
graph = [[0 for _ in range(200)] for _ in range(200)]
all_edge = deque()
move_rule = {
0: [0,1], 1: [-1,0], 2: [0,-1], 3: [1,0]
}
dragon_rule = {
0:1,1:2,2:3,3:0
}
move = []
for _ in range(N):
move = []
x, y, d, g = map(int, input().split())
# 다음 움직일 장소 정렬
cur_move = move_rule[d]
ny, nx = y + cur_move[0], x + cur_move[1]
graph[y][x], graph[ny][nx] = 1, 1
if not([y,x] in all_edge) :
all_edge.append([y,x])
if not([ny,nx] in all_edge) :
all_edge.append([ny,nx])
last = [ny, nx]
move.append(d)
for _ in range(g) :
tmp = len(move) - 1
for m in range(tmp, -1, -1) :
# 다음 이동 결정
nm = dragon_rule[move[m]]
move.append(nm) # 움직인 방향 추가
cur_move = move_rule[nm]
# 다음 장소로 이동 후 저장
ny, nx = last[0] + cur_move[0], last[1] + cur_move[1]
if not ([ny, nx] in all_edge) :
all_edge.append([ny, nx])
graph[ny][nx] = 1
last = [ny,nx] # 마지막 움직인 곳 변경
cnt = 0
def check(v1, v2, v3, v4) :
global cnt
if graph[v1[0]][v1[1]] and graph[v2[0]][v2[1]] and graph[v3[0]][v3[1]] and graph[v4[0]][v4[1]] :
cnt += 1
while all_edge :
y, x = all_edge.popleft()
check([y,x], [y+1, x], [y+1, x+1], [y,x+1])
print(cnt)다른 사람 풀이
애초에 움직임 타입과 움직임별 커브 방향 등을 hash table로 들고 있다가 구현하는 방식을 선택했는데, 이 사람은 리스트 자료형의 특성을 잘 이용해서 움직임 타입을 인덱스로 지정해서 만약에 타입 1번이면 dx[1], dy[1] 이므로 왼쪽으로 움직이도록 구현을 했고 각 움직임 타입별로 커브 방향은 q = [(i + 1) % 4 for i in temp]라는 간단한 연산으로 계산했다.
그리고 정사각형이 있는지는 모든 점들을 돌면서 계산하는 방식을 선택했는데 이 부분만 조금 비효율적으로 느껴졌다.
import sys
input = sys.stdin.readline
# 동-북-서-남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
if __name__ == "__main__":
n = int(input())
board = [[0] * 101 for _ in range(101)]
for _ in range(n):
# ⚠️ 좌표 주의! 문제에서는 가로가 x, 세로가 y
# 근데 일반적으로 나는 문제를 풀때 가로가 y, 세로가 x이므로 순서 전환 필요
y, x, d, g = map(int, input().split())
board[x][y] = 1
temp = [d]
q = [d] # 이동방향
for _ in range(g + 1): # 0~g세대
for k in q:
x += dx[k]
y += dy[k]
board[x][y] = 1
q = [(i + 1) % 4 for i in temp]
q.reverse()
temp = temp + q
result = 0
for i in range(100):
for j in range(100):
if (
board[i][j]
and board[i][j + 1]
and board[i + 1][j]
and board[i + 1][j + 1]
):
result += 1
print(result)다른 사람 풀이 개선 버전
다음과 같이 개선을 했다고 생각을 했는데 오히려 수행시간이 늘어났다. 이유를 짐작해보자면 in 연산이 생각보다 시간을 많이 잡아먹는다는 생각이 들었다.
import sys
from collections import deque
input = sys.stdin.readline
# 동-북-서-남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
if __name__ == "__main__":
n = int(input())
board = [[0] * 102 for _ in range(102)]
queue = deque()
for _ in range(n):
# ⚠️ 좌표 주의! 문제에서는 가로가 x, 세로가 y
# 근데 일반적으로 나는 문제를 풀때 가로가 y, 세로가 x이므로 순서 전환 필요
y, x, d, g = map(int, input().split())
board[x][y] = 1
if not ([x,y] in queue):
queue.append([x,y])
temp = [d]
q = [d] # 이동방향
for _ in range(g + 1): # 0~g세대
for k in q:
x += dx[k]
y += dy[k]
board[x][y] = 1
if not ([x,y] in queue):
queue.append([x,y])
q = [(i + 1) % 4 for i in temp]
q.reverse()
temp = temp + q
result = 0
while queue:
x, y = queue.popleft()
if board[x][y] and board[x + 1][y] and board[x + 1][y + 1] and board[x][y + 1]:
result += 1
print(result)