nice!

[백준 15685번] 드래곤 커브 - Python으로 구현하기

문제 접근

• 규칙성을 찾아봐야 하는 문제

* 드래곤 커브의 규칙은 다음과 같다.

방향이 0 인 드래곤 커브의 세대별 방향 정보 규칙

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

...

그 전 세대의 reverse로 +1 씩 증가하는 형태이다.

생각해볼 점

• 규칙없이 풀 수 있을까? 단순 구현으로!

오답 분석

• x,y 좌표가 행렬의 row,col과 반대로 주어져 그림이 잘못 그려질 수 있다. 주의!

N = int(input())
map_data = [[1]*101 for _ in range(101)]
di = {0:[0,1],1:[-1,0],2:[0,-1],3:[1,0]}
for _ in range(N):
    x,y,d,g,=map(int,input().split())

    curve_info=[d]
    for _ in range(g):
        curve_info += [(i+1)%4 for i in curve_info[::-1]]
    map_data[y][x]=0
    nx=x
    ny=y
    print(curve_info)
    for curve in curve_info:
        nx=nx+di[curve][1]
        ny=ny+di[curve][0]
        map_data[ny][nx]=0

for i in map_data:
    print(i)

# 정답 구하기
cnt=0
for i in range(100):
    for j in range(100):
        if map_data[i][j]+map_data[i][j+1]+map_data[i+1][j]+map_data[i+1][j+1]==0:
            cnt+=1
print(cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 15686번] 치킨 배달 - Python으로 구현하기

문제 접근

• O(13Cm*N*N)의 시간복잡도로 구할 수 있다.
• 집의 좌표, 치킨집의 좌표를 모두 저장해 둔 뒤, 주어진 공식대로 최단거리를 찾으면 된다

생각해볼 점

• 시간복잡도를 고려하지않고 BFS로 접근했다가 실패했다. 시간복잡도를 꼭 고려하기!

오답 분석

• 최단 거리 구할 때 시간초과 조심

from itertools import combinations as cm
import math

N,M = map(int,input().split())
map_data = [list(map(int,input().split())) for _ in range(N)]
chi = []
home = []
for i in range(N):
    for j in range(N):
        if map_data[i][j]==2:
            map_data[i][j]=0
            chi.append([i,j])
        elif map_data[i][j]==1:
            home.append([i,j])
ans=math.inf
for now_chi in cm(chi,M):
    now_sum=0
    for h in home:
        dist=math.inf
        for k in now_chi:
            dist=min(dist,abs(h[0]-k[0])+abs(h[1]-k[1]))
        now_sum+=dist
    ans=min(ans,now_sum)
print(ans)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 16234번] 인구 이동 - Python으로 구현하기

문제 접근

• BFS로 주어진 조건과 연결된 노드들을 숫자로 표시해주자
• 노드들을 연결하면서 합과 개수를 구해 딕셔너리에 보관하자
• 행렬을 돌면서 자신의 union에 맞는 합과, 개수를 나누어 갱신해주자

생각해볼 점

• 종료조건이 괜찮은지?

오답 분석

• 연합개수*N*N 으로 구하지 않도록 주의, 메모리를 사용하자!

from collections import deque

def find_union(start,num):
    dq = deque()
    dq.append(start)
    union[start[0]][start[1]]=num
    union_sum=A[start[0]][start[1]]
    union_cnt=1
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]

            if 0<=nx<N and 0<=ny<N and union[nx][ny]==-1 and L<=abs(A[x][y]-A[nx][ny])<=R:
                union_sum+=A[nx][ny]
                union[nx][ny]=num
                union_cnt+=1
                dq.append([nx,ny])
    return [union_sum,union_cnt]

N,L,R=map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]

di = [[-1,0],[0,-1],[1,0],[0,1]]
cnt=0
while True:
    union = [[-1] * N for _ in range(N)]
    n=0
    union_info={}
    for i in range(N):
        for j in range(N):
            if union[i][j]==-1:
                union_info[n]=find_union([i,j],n)
                n+=1

    if n==N*N:    # 모든 국경선이 열리지 않음
        break

    # 국경 업데이트
    for i in range(N):
        for j in range(N):
            A[i][j]=union_info[union[i][j]][0]//union_info[union[i][j]][1]
    cnt+=1
print(cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 16235번] 나무 재테크 - Python으로 구현하기

문제 접근

• 봄,여름,가을,겨울 주어진 조건대로 구현하기
• 나무의 나이를 리스트로 만들어 2D에 저장 하여 구현하자

생각해볼 점

• 가을에 나무가 확산 될 때 리스트의 앞에 넣으면 정렬을 반복 할 필요가 없을 것 같다.

오답 분석

• 여름에서 나무의 나무를 증가시키고 양분을 제거하는 실수를 범했다. 찾기 엄청 힘들었다..
•  

N,M,K=map(int,input().split())  # n:n*n, m개 나무 k년
A = [list(map(int,input().split())) for _ in range(N)]
tree = [[[] for _ in range(N)] for _ in range(N)]

for _ in range(M):
    x,y,z=map(int,input().split())
    tree[x-1][y-1].append(z)

ground = [[5]*N for _ in range(N)]

for _ in range(K):
    # 봄
    for i in range(N):
        for j in range(N):
            if len(tree[i][j])<=0: continue
            tree[i][j].sort()
            idx=0
            while idx<len(tree[i][j]):
                if tree[i][j][idx]<=ground[i][j]:
                    ground[i][j]-=tree[i][j][idx]
                    tree[i][j][idx] += 1
                    idx+=1
                else:
                    die = tree[i][j][idx:]
                    for now in die:    # 죽은나무!
                        ground[i][j]+=(now//2)
                    tree[i][j]=tree[i][j][:idx]
                    break

    # 가을
    di = [[-1,0],[0,-1],[1,0],[0,1],[1,1],[1,-1],[-1,1],[-1,-1]]
    for i in range(N):
        for j in range(N):
            c=0
            if tree[i][j]:
                for now in tree[i][j]:
                    if now%5==0:
                        c+=1
            if c>0:
                for k in range(8):
                    ni=i+di[k][0]
                    nj=j+di[k][1]
                    if 0<=ni<N and 0<=nj<N:
                        for _ in range(c):
                            tree[ni][nj].append(1)

    # 겨울
    for i in range(N):
        for j in range(N):
            ground[i][j]+=A[i][j]

ans=0
for i in range(N):
    for j in range(N):
        ans+=len(tree[i][j])
print(ans)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 16236번] 아기 상어 - Python으로 구현하기

문제 접근

• 정해진 규칙에 따라 아기 상어의 다음 위치를 정해주어야 한다.
• 거리가 같은 먹을 수 있는 곳이 여러 개인 경우 가장 높고, 가장 왼쪽에 있는 좌표로 이동한다.

생각해볼 점

• 짜다보니 하드코딩을 해버렸다. baby shark의 정보들을 깔끔하게 관리하고, 로직도 다시 생각해봐야 겠다.

오답 분석

• 거리가 같은 상어들의 우선순위를 정해주지 않으면 오답!

def find_shark(baby):
    global map_data,baby_pos,baby_size,baby_eat_cnt,time

    dq = deque()
    dq.append(baby)
    dist = [[-1] * N for _ in range(N)]
    dist[baby[0]][baby[1]]=0
    min_dist=N*N

    while dq:
        x,y=dq.popleft()

        for k in range(4):
            nx = x+di[k][0]
            ny = y+di[k][1]

            if 0<=nx<N and 0<=ny<N and dist[nx][ny]==-1 and map_data[nx][ny]<=baby_size:
                dist[nx][ny]=dist[x][y]+1
                dq.append([nx,ny])
                if 0<map_data[nx][ny]<baby_size:
                    min_dist=min(min_dist,dist[nx][ny])

    next_pos=[]
    for i in range(N):
        for j in range(N):
            if dist[i][j]==min_dist and 0<map_data[i][j]<baby_size:
                next_pos.append([i,j])

    if next_pos:
        next_pos.sort(key=lambda x:(x[0],x[1]))
        baby_pos=next_pos[0]
        baby_eat_cnt+=1
        time += min_dist
        map_data[baby_pos[0]][baby_pos[1]]=0
        return True
    else:
        return False


from collections import deque

N = int(input())
map_data = [list(map(int,input().split())) for _ in range(N)]

baby_size = 2
baby_pos = [0,0]
baby_eat_cnt = 0
di = [[-1,0],[0,-1],[0,1],[1,0]]

for i in range(N):
    for j in range(N):
        if map_data[i][j]==9:
            baby_pos=[i,j]
            map_data[i][j]=0
            break

time = 0
while True:
    if not find_shark(baby_pos):
        break
    if baby_eat_cnt==baby_size:
        baby_eat_cnt=0
        baby_size+=1
print(time)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 17144번] 미세먼지 안녕! - Python으로 구현하기

문제 접근

• 주어진 순서대로 확산 -> 순환 과정을 구현하면 된다.
• 확산 과정 : 임의 tmp 배열에 확산된 값을 저장하고(동시에 확산하기 때문에) 확산이 끝나면 기존 미세먼지값에 업데이트 해준다. 또한, 주어진 수식에 따라 확산양*확산된 곳 개수 을 빼준다.
• 순환 과정 : 배열의 테두리를 돌려야한다. 임의 tmp 배열 하나를 생성해두어 간단하게 처리 가능하다.(모서리부분 주의)

생각해볼 점

• 배열 테두리를 돌리는데 더 나은 방법?

R,C,T=map(int,input().split())
A = [list(map(int,input().split())) for _ in range(R)]
di = [[-1,0],[0,-1],[1,0],[0,1]]
time = 0
while time<T:
    # 미세먼지 확산
    tmp_A = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if A[i][j]>0:
                cnt = 0
                for k in range(4):
                    ni=i+di[k][0]
                    nj=j+di[k][1]
                    if 0<=ni<R and 0<=nj<C and A[ni][nj]!=-1:
                        tmp_A[ni][nj]+=(A[i][j]//5)
                        cnt+=1
                A[i][j]=A[i][j]-(A[i][j]//5)*cnt

    # 기존 A와 확산 미세먼지 합치기
    for i in range(R):
        for j in range(C):
            A[i][j]+=tmp_A[i][j]

    # 공기청정기 순환
    tmp_A = [[-2] * C for _ in range(R)]
    up_machine_row=0
    for row in range(R):
        if A[row][0]==-1:
            up_machine_row=row
            break
    # 위쪽
    for i in range(1,C):
        tmp_A[0][i-1]=A[0][i]
        tmp_A[up_machine_row][i]=A[up_machine_row][i-1]
        tmp_A[up_machine_row][1]=0
    for i in range(1,up_machine_row+1):
        if A[i][0]!=-1:
            tmp_A[i][0]=A[i-1][0]
        tmp_A[i-1][C-1]=A[i][C-1]


    # 아래쪽
    for i in range(1,C):
        tmp_A[R-1][i-1]=A[R-1][i]
        tmp_A[up_machine_row+1][i]=A[up_machine_row+1][i-1]
        tmp_A[up_machine_row+1][1]=0
    for i in range(up_machine_row+2,R):
        if A[i-1][0]!=-1:
            tmp_A[i-1][0]=A[i][0]
        tmp_A[i][C-1]=A[i-1][C-1]

    for i in range(R):
        for j in range(C):
            if tmp_A[i][j]!=-2:
                A[i][j]=tmp_A[i][j]
    time+=1

print(sum(list(sum(A,[])))+2)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 17143번] 낚시왕 - Python으로 구현하기

문제 접근

• 주어진 문제대로 구현하는 구현 문제.
• 상어가 속력만큼 움직이는 것을 구현해야 하는데, 아래 규칙을 보면 반복문 횟수를 줄일 수 있다.
• [0] ~ [k] ~ [n-1] : k에 있는 상어가 n-1으로 갔다가 회전하여 0을 찍고 다시 k로 돌아오는건 (n-1-k) + (n-1) + (k) = 2*n-2이다. 따라서 상어가 움직일 수 있는 범위는 속력%(2*n-2)
• 아직 안움직인 상어를 잡어먹을 순 없으므로 새로운 2D 배열로 움직인 상어들을 저장, 비교

생각해볼 점

• 상어의 움직이는 처리를 좀더 깔끔하게 할 수 없을지?
• 하드 코딩으로 풀었는데, 다른 로직이 없는지 생각해보기

오답 분석

• 시간 초과가 많이 나는 문제로, 주어진 반복문을 최적화 할 수 있어야한다.

def catch_shark():
    global catch_cnt
    for row in range(R):
        if map_data[row][person]:
            catch_cnt+=map_data[row][person][2]
            map_data[row][person]=[]
            return

def shark_move():
    global map_data
    tmp_shark = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if map_data[i][j]:
                direction = map_data[i][j][1]
                ni=i
                nj=j
                if 1<=direction<=2: # 세로방향
                    for _ in range(map_data[i][j][0]%(2*len(map_data)-2)):
                        ni=ni+di.get(direction)[0]
                        nj=nj+di.get(direction)[1]
                        if ni==-1 or ni == len(map_data):    # 끝까지 간 경우 방향전환
                            direction= 2 if direction==1 else 1
                            ni = ni + di.get(direction)[0]
                            ni = ni + di.get(direction)[0]
                            map_data[i][j][1]=direction

                elif 3<=direction<=4: # 가로방향
                    for _ in range(map_data[i][j][0]%(2*len(map_data[0])-2)):
                        ni=ni+di.get(direction)[0]
                        nj=nj+di.get(direction)[1]
                        if nj==-1 or nj == len(map_data[0]):
                            direction = 4 if direction == 3 else 3
                            nj = nj + di.get(direction)[1]
                            nj = nj + di.get(direction)[1]
                            map_data[i][j][1] = direction

                if tmp_shark[ni][nj]:   # 이미 상어가 있는 경우
                    if tmp_shark[ni][nj][2]<map_data[i][j][2]:
                        tmp_shark[ni][nj] = map_data[i][j]
                else:
                    tmp_shark[ni][nj] = map_data[i][j]
    map_data=tmp_shark


R,C,M = map(int,input().split())
map_data = [[[] for _ in range(C)] for _ in range(R)]
di = {1:[-1,0],2:[1,0],3:[0,1],4:[0,-1]}

for _ in range(M):
    r,c,s,d,z = map(int,input().split())
    map_data[r-1][c-1]=[s,d,z]

person=-1
catch_cnt=0
while person<C-1:
    person+=1   # 사람을 오른쪽 열로 이동
    catch_shark()
    shark_move()
print(catch_cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 17140번] 이차원 배열과 연산 - Python으로 구현하기

문제 접근

• 행과 열에 대한 연산을 구현해야 되는 경우에는 행에 대한 연산 구현 후 transpose 하여 열도 처리한다.
• 주어진 조건이 많으므로 차근차근히 구현해야한다.
• 행의 정수 빈도 수는 collections 모듈의 Counter를 사용하자.

생각해볼 점

• transpose하지 않고 구하기

오답 분석

• Counting 할때 0을 제거하지 않으면 오답!
• 100개까지만 취급하는 조건 주의
• time이 100인 경우에도 확인 해야한다.

from collections import Counter

r,c,k=map(int,input().split())
A = [list(map(int,input().split())) for _ in range(3)]

r-=1	# 0 index
c-=1
time=0	# 시간
while time<=100:
    if r<len(A) and c<len(A[0]) and A[r][c]==k:	# 정답 확인
        print(time)
        break

    # C연산인 경우 : transpose
    C_flag=False
    if len(A)<len(A[0]):
        C_flag=True
        A=list(zip(*A))

    # row에 대한 주어진 연산 구현
    max_len=0
    tmp_a = []
    for now_row in A:
        ct = Counter(now_row)
        if ct.get(0):	# 0은 카운팅하지 않음!
            del ct[0]
        num_cnt = list(map(list,ct.items()))
        num_cnt.sort(key=lambda x :(x[1],x[0]))		# 주어진 순서대로 정렬
        tmp_a.append(list(sum(num_cnt,[]))[:100])	# 100개를 초과하는 경우 100개 까지만
        max_len=max(max_len,len(tmp_a[-1]))

    for i in range(len(tmp_a)):
        if len(tmp_a[i])<max_len:
            tmp_a[i]+=[0]*(max_len-len(tmp_a[i]))	# 길이 맞춰주기

    A=tmp_a

    if C_flag:		# C연산 인경우 다시 transpose
        A=list(zip(*A))
    time+=1

if time>100:
    print(-1)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!