[백준 15685번] 드래곤 커브

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

(문제 자체가 상당히 길기 때문에

문제는 링크를 참고부탁드릴게요.)

 

이 문제를 푸는 방식은 크게 이렇게 됩니다.

 

1. 0으로 이루어진 그래프 만들기

2. 각각 드래곤 커브를 만들면서 그래프에 1을 입력하기

3. 그래프를 돌면서 정사각형을 찾는다.

 

참 쉽죠?간단하게 끝!이라고 말하면 너무 날먹...여기서 가장 큰 관건은'그래서 어떻게 드래곤 커브를 그릴 건데?'이 드래곤 커브의 규칙이 상당히 난해해서처음보는 입장에서는 좀 셧터퍼킹합니다.

처음에 다른 문제처럼

뭐야 회전?

d=(d+1)%4 하면 되겠네?했다가 값이 미친듯이 높게 나오길래많이 당황했습니다.처음엔 이게 뭐지 싶다가모범답안을 힌트처럼 돌아보니제가 커브를 잘못 그렸더군요.다시 차근차근 커브를 보니저렇게 역으로 더해주는 것이 보입니다.90도를 시계방향으로 회전에서 그려주므로1을 더한다는 것이 얼추 감이 옵니다.

N = int(input())
dragon = []
for i in range(N):
    dragon.append(list(map(int, input().split())))

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]  # 방향키 

mapping = [[0] * 101 for _ in range(101)]  # mapping그리기

ans = 0
for i in range(N):
    now_y = dragon[i][1]
    now_x = dragon[i][0]
    d = dragon[i][2]
    g = dragon[i][3]
    mapping[now_y][now_x] = 1
    # 드래곤 각각에 대해서 현재위치,방향,g를 받음
    curve = [d]
    for j in range(g):
        for x in range(len(curve) - 1, -1, -1):
            curve.append((curve[x] + 1) % 4)
    # 드래곤 커브를 받음. 뒤부터 역순으로 1더한다는 것을 생각.
    for k in range(len(curve)):
        now_y += dy[curve[k]]
        now_x += dx[curve[k]]
        if now_x < 0 or now_x >= 100 or now_y < 0 or now_y >= 100:
            continue

        mapping[now_y][now_x] = 1
        print(now_y, now_x, i)

for i in range(100):
    for k in range(100):
        if mapping[i][k] == 1 and mapping[i + 1][k] == 1 and mapping[i][k + 1] == 1 and mapping[i + 1][k + 1] == 1:
            ans += 1

print(ans)

저의 코드입니다.

저는 먼저 dragon을 다 받고 

다시 꺼냈습니다만

예시답안을 보니

굳이 그렇게 하지 않고

바로바로 하나씩 그리는 방식도 있네요.

(이렇게 하는 것이 더 간단하고 오히려 문제의도에 더 맞는 느낌)

이 문제는 좌표평면의 개념을 떠올리면

어느정도 아이디어 유추가 가능하지만

커브를 그리는 규칙찾는 게 생각보다 어려운 문제였습니다.

+++++

 

하나 하나 그리면서

바로 구하는 방식의 코드입니다.

 

위의 코드도 괜찮긴 한데

가독성측면에서는

그리면서 보는 게 더 좋다고 느껴졌습니다.

그래서 direct이라는 리스트에

움직인 방향을 받았습니다.

그리고 다음 세대를 그릴 때

현재 direct리스트에서

가장 끝에서부터 처음꺼까지 역으로 받아가면서

90도 회전을 시키는 걸로 움직였습니다.

#백준 15685번 드래곤커브

N=int(input())

points=[[0]*101 for _ in range(101)]

#드래곤  커브 방향
dy=[0,-1,0,1]
dx=[1,0,-1,0]


for _ in range(N):
  x,y,d,g=map(int,input().split())

  ny,nx=y,x

  points[ny][nx]=1
  #먼저,g==0일 경우 먼저.
  direct=[d]
  ny+=dy[d]
  nx+=dx[d]
  points[ny][nx]=1

  #g가 1이상 클 경우

  for turn in range(g):
    now_len=len(direct)
    for move in range(now_len-1,-1,-1):
      now_d=direct[move]
      now_d=(now_d+1)%4
      ny+=dy[now_d]
      nx+=dx[now_d]
      points[ny][nx]=1
      direct.append(now_d)#새로 집어넣어야 다음 세대에서도 이용가능
  #print(direct)


#print(points)
count=0
for y in range(100):
  for x in range(100):
    if points[y][x]==1 and points[y][x+1]==1 and points[y+1][x]==1 and points[y+1][x+1]==1:
       count+=1

print(count)

 

https://chldkato.tistory.com/150

백준 15685 드래곤 커브 (파이썬)

대부분의 인터넷 솔루션을 보면

'리스트를 활용해서

90도 회전시키는'

개념을 잘 활용하는 게 많았습니다.

각자 편하신데로

돌리는 걸 구현하시면 좋을 것 같습니다.

 

(내용추가 업데이트:2022.10.14)

dx=[0,-1,0,1]
dy=[1,0,-1,0]
N=int(input())

curve=[set()]

visited=[[False]*100 for _ in range(100)]

def graph(x,y,d,g):

    point=set()
    point.add((x,y))
    p=[(d+1)%4]
    x+=dx[d]
    y+=dy[d]
    point.add((x,y))
    for t in range(g):
        l_p=len(p)
        trace=[]
        for k in range(l_p-1,-1,-1):
            nd=p[k]
            x+=dx[nd]
            y+=dy[nd]
            point.add((x,y))
            trace.append(nd)
            nd=(nd+1)%4
            p.append(nd)





    return point

for num in range(1,N+1):
    x,y,d,g=map(int,input().split())
    now=graph(y,x,d,g)
    curve.append(now)
squre=set()
for num in range(1,N+1):

    for px,py in curve[num]:
        #혹시나 커브에서 범위 초과한게 있으면 넘기려고 이렇게 다 받고 좌표받는걸로 설정해둠
        if px<0 or px>100 or py<0 or py>100:
            continue

        squre.add((px,py))
cnt=0
for x in range(100):
    for y in range(100):
        if (x,y) in squre and (x+1,y) in squre and (x,y+1) in squre and (x+1,y+1) in squre:
            cnt+=1

print(cnt)

이번에는 좌표를 배열에 받는 게 아니라

집합에 받고 풀어봤습니다.

혹시나 커브를 돌다가

범위를 벗어나는 게 있을 경우를 대비해서

모든 커브의 경우를 다 받고

좌표를 넣어주는 방식으로 구했습니다.

그 후, 0~100까지의 좌표를 돌면서

x y 

x+1 y

x y+1

x+1 y+1

각각이 

집합에 있는지 확인해주고

있다면 1x1사각형이 된다는 의미이므로

cnt+=1을 해줬습니다.

이 방식이 혹시나 배열 탐색하다가

범위초과가 뜰 걱정도 없어서 더 편한 느낌이네요.