[2021 삼성 코딩테스트 상반기 오전 2번] 코드트리 - 색깔 폭탄 파이썬

https://www.codetree.ai/training-field/frequent-problems/problems/colored-bomb?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

아..

 

삼성 코딩테스트 10월 15일 오후2시30분 전 ...

 

마지막 신문제 도전..............................

결국 통과했다. 

 

아까한 3~4시간 정도 집중못하다가 

어디가 틀렸나 테스트 하고 

겨우 if문 잔뜩 중첩돼있는곳에서 에러가 난걸 찾아서 

해결했다.

 

하.. 만약 실전에서 저런류의 if문 에러가 나버린다면..? 

 

아 이제는 IDE써서 디버깅할줄아니까 그래도 시간박으면 찾을 수 있을꺼같다. 

테스트 케이스가 거지같이만 안주어진다면.. 

거기선 내가 엣지케이스를 만들수밖에없다. 

 

이문제를 풀면서 

구현에있어서 조금 어려웠던게 있다. 

 

1. 2차원배열 중력으로 떨어지게 하는것 + 돌이있으면 걸려야함 

 

 

2. 우선순위에 따라서 조건별로 최대값 뽑아내는거 (if문 지옥) 

 

나머지 회전은 딱히 어렵진 않았고

전체적으로 어떻게 짜야 계속 돌아가게 할 수있나를 잘 고려했다. 

while 문을 사용하지만, 

만약 빈 배열을 리턴하면 break하게 작성했다. 

 

 

---

 

1. 2차원배열 중력으로 떨어지게 하는것 + 돌이있으면 걸려야함 

 

이부분은 처음에 투포인터? 라고 부르던데.. 

인터넷에 관련글을 찾아보니 뭔가 각자 다른방식으로 하고있고

나는 명확히 떠오르는방법이 이거라서 이거로 구현해봤다. 

 

 

 

이렇게 배열을 가장 아래에서 부터 탐색을하는데, 

insert에 넣을 녀석을 check가 위로 올라가면서 탐색하는것이다. 

-2가 빈공간인데 빈공간이면 그냥 continue 로 check를 위로 이동. 

 

 

check는 (insert,-1,-1) 의 길이로 탐색을 하는데 올라가다가 만약 폭탄을 발견하면, 

is_insert 라는 배열에 넣고 ( 이미 해당인덱스는 넣었다. ) 

temp 맵의 insert 에 check 부분을 넣는다. 

 

만약 공중에 떠있는 돌이였으면 해당 순차는 break하고 하고 그다음꺼를 탐색한다. 

즉, 공중에 돌이 떠있는게 계속 위의 인덱스에 걸리니까 돌을 넘어갈때까지 

돌보다 높은 인덱스를 내릴 수 없게 했다. 

 

해당 부분만 보면 코드는 

for col in range(n) :         is_insert=[]         for insert in range(n-1,-1,-1) :             for chk in range(insert,-1,-1):                 if maps[chk][col] == -2 : continue                 elif maps[chk][col] == -1 : #만약돌바위면?                     break # break                 else :                     if not chk in is_insert:                         temp_maps[insert][col] = maps[chk][col]                         is_insert.append(chk)                         break

이다 is_insert를 각 행마다 초기화 시켜주고, 

올라가면서 체크를 실행하고, 만약 is_insert에 없으면 넣어주고 is_insert 배열에 넣어 중복을 방지해주고 break한다.

insert에 넣게 되면 중지한다는것. 

 

대체 이걸 어떻게 짰을까? 내가 다시봐도 신기하다 ㅋㅋ

무튼 이 알고리즘으로 clear.

 

---

2. 우선순위에 따라서 조건별로 최대값 뽑아내는거 (if문 지옥) 

 

이부분이 이제 마지막 디버깅에서 상당히 애를 먹게 해줬는데.. 

 

 

for i in range(n) :         for j in range(n) :             if maps[i][j] >= 0 :                 (br,bx,by,barr,bcnt) = bfs(i,j)                 if br == bcnt : continue                 #br빨간색폭탄의                 if bcnt >= 2 :                         if max_cnt < bcnt :                         max_cnt = bcnt                         if br < min_red_bomb_cnt :                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                         elif br == min_red_bomb_cnt :                             if max_x < bx :                                 min_red_bomb_cnt = br                                 max_x,min_y = bx,by                                 min_arr = barr                             elif max_x == bx :                                 if min_y > by :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr                                 else :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr                         else : #크기가 크니까 바로 갱신해줘야함.                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                     elif max_cnt == bcnt:                         if br < min_red_bomb_cnt :                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                         elif br == min_red_bomb_cnt :                             if max_x < bx :                                 min_red_bomb_cnt = br                                 max_x,min_y = bx,by                                 min_arr = barr                             elif max_x == bx :                                 if min_y > by :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr

그냥 말하면 

bfs를 통해서 빨간폭탄개수,가장 왼쪽x,가장왼쪽y,방문배열,폭탄개수 를 리턴 받고, 

가져온 놈들에서 폭탄개수는 2개 이상, 만약 폭탄개수와 빨간폭탄개수가 같으면 continue, 

최대 폭탄개수를 초과하면 폭탄개수를 올려주고 빨간폭탄개수를 비교한다.

( 폭탄개수 4개 빨폭 3개 vs 폭탄개수 3 개면, 폭탄개수 4개가 이기니까 ) 

 

만약 빨간폭탄이 더작으면 그녀석을 써주고, 

빨간폭탄이 같을때 

max_x와 min_y 를 차례대로 비교해준다. 내가 실수 했던 부분이 

max_x는 같고 min_y 를 비교할때, min_y보다 by 가 작을때만 넣어줬어야했는데 min_y 가 by보다 클때도 넣어줘버려서

이걸 찾는데 한참걸렸다 헤엑~~~

 

찾아보니까 

minV, maxT, minI, minJ = a[i][j], lastAttack[i][j], i, j

 

이런식으로 깔끔하게 업데이트 해주던데, 저렇게 써서 가독성을 높여봐야겠다. 

 

해당 위부분은 다양한 조건이 걸러질때 특이 케이스를 넣어서 검출해보자. 

예를들어 조건문에 걸러지고 걸러지고 걸러지고 의 케이스를 

엣지케이스로 넣어보자. 

 

 

 

내일 오후2시30분... 마지막으로 블로그 글 리뷰해보고 다녀오겠다...

 

 

 

from collections import deque import sys sys.stdin = open("input_색깔폭탄.txt",'r') n,m = map(int,input().split()) deb = 0 maps = [ list(map(int,input().split())) for _ in range(n)] dxs=[0,0,-1,1] dys=[-1,1,0,0] def in_range(x,y) :     return 0<=x<n and 0<=y<n def down_maps(): #  중력다운시키기     temp_arr = deque()     temp_maps = [ [-2]*n for _ in range(n)]     check = n-1     for col in range(n) :         is_insert=[]         for insert in range(n-1,-1,-1) :             for chk in range(insert,-1,-1):                 if maps[chk][col] == -2 : continue                 elif maps[chk][col] == -1 : #만약돌바위면?                     break # break                 else :                     if not chk in is_insert:                         temp_maps[insert][col] = maps[chk][col]                         is_insert.append(chk)                         break                     for i in range(n) :         for j in range(n) :             if maps[i][j] == -1 :                 temp_maps[i][j] = -1     if deb:         print(temp_maps)     for i in range(n) :         for j in range(n) :             maps[i][j] = temp_maps[i][j]     return def rotate_maps() :     temp = [ [0]*n for _ in range(n)]     for i in range(n) :         for j in range(n) :             temp[i][j] = maps[i][j]     for i in range(n) :         for j in range(n) :             maps[n-j-1][i] = temp[i][j]     if deb:         print(maps)     return def bfs(x,y) :     bomb_cnt =1     visited = [ [-2]*n for _ in range(n)]     queue = deque()     queue.append((x,y))     color = maps[x][y]     visited[x][y] = color     red_bomb_cnt = 0     if color == 0 :         red_bomb_cnt = 1     # 정확히 2개의 색깔? 만약 걸리면 확인     while queue:         x,y = queue.popleft()         for i in range(4) :             nx,ny = x+dxs[i],y+dys[i]             if in_range(nx,ny) and visited[nx][ny] == -2 :                 if  (maps[nx][ny] == 0 ) : #빨간돌이 들어갔다?                     red_bomb_cnt += 1                     bomb_cnt += 1                     queue.append((nx,ny))                     visited[nx][ny] = maps[nx][ny]                 elif  maps[nx][ny] == color:                     queue.append((nx,ny))                     bomb_cnt += 1                     visited[nx][ny] = maps[nx][ny]     bx,by = 0,0         for i in range(n) :         for j in range(n):             if visited[i][j] > 0:                 if bx < i :                     bx,by = i ,j                 elif bx == i :                     if j < by :                         bx,by = i,j         return (red_bomb_cnt,bx,by,visited,bomb_cnt) def find_bombs() :     # 폭탄 개수가 커야함. ( 2개이상 )     # 같은색 폭탄 or 빨간색 + 다른색     #     min_red_bomb_cnt = 100000     max_x,min_y = 1000,1000     min_arr = []     max_cnt = 0     for i in range(n) :         for j in range(n) :             if maps[i][j] >= 0 :                 (br,bx,by,barr,bcnt) = bfs(i,j)                 if br == bcnt : continue                 #br빨간색폭탄의                 if bcnt >= 2 :                         if max_cnt < bcnt :                         max_cnt = bcnt                         if br < min_red_bomb_cnt :                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                         elif br == min_red_bomb_cnt :                             if max_x < bx :                                 min_red_bomb_cnt = br                                 max_x,min_y = bx,by                                 min_arr = barr                             elif max_x == bx :                                 if min_y > by :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr                                 else :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr                         else : #크기가 크니까 바로 갱신해줘야함.                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                     elif max_cnt == bcnt:                         if br < min_red_bomb_cnt :                             min_red_bomb_cnt = br                             max_x,min_y = bx,by                             min_arr = barr                         elif br == min_red_bomb_cnt :                             if max_x < bx :                                 min_red_bomb_cnt = br                                 max_x,min_y = bx,by                                 min_arr = barr                             elif max_x == bx :                                 if min_y > by :                                     min_red_bomb_cnt = br                                     max_x,min_y = bx,by                                     min_arr = barr     if deb :         print(min_red_bomb_cnt,max_x,min_y,min_arr,max_cnt)         return min_arr # -1 검은돌, 0 은 빨간색폭탄 # 빨간색 폭탄을 포함하고 색깔 1개 해서 총 2개여야만 연걸되어있음. # 모두 같은 색깔의 폭탄으로만 이루어져있어야함 . def delete_arr_maps(arr) :     cnt = 0     for i in range(n) :         for j in range(n) :             if arr[i][j] != -2 :                 cnt +=1                 maps[i][j] = -2     return cnt possible = True answer = 0 while possible :     point =0     visit_arr = find_bombs()     if len(visit_arr) == 0 :         break     point += delete_arr_maps(visit_arr)     answer += (point)**2     down_maps()     rotate_maps()     down_maps() print(answer) # 가장큰 폭탄묶음은, 가장 많은수로 이루어진 폭탄묶음을 의미. # 폭탄묶음이 여러개면 # 1. 빨간폭탄 가장적게 # 2. 만약 빨간폭탄 개수가 여러개면, 묶음 기준점중 가장 행이 큰 폭탄 묶음 빨간색이 아니고, 행이 가장큰 칸을 의미. 행이 크고 열이 가장 적은거 아래부터 왼쪽으로 탐색하기 # 3. 폭탄들 전부 제거, 그다음 중력작용하여 위에있는애들 떨어지지만, 돌들은 떨어지지 않는다. # 4. 반시계 방향으로 90도 판에 회전 # 5. 다시 중력이 작용. # 6. 폭탄묶음 존재하지않을때까지 반복. # - 한 라운드에서 폭탄개수가 c면 제곱만큼 점수 얻기.