코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
DFS와 Simulation 유형의 기출문제이다.
처음에 DFS가 나와있어서 어라.. 나 BFS만 잔뜩 해봤는데 풀 수 있나 했더니
역시 DFS가 되면 bfs로도 상관없이 되더라.
이번 문제를 풀며 힘들었던 점? 이랄까
를 정리해보면
1.각 팀을 어떻게 저장할 것이고, 관리할 것인지? + move 할때 방향
2. 라운드 마다 던져지는 공의 점화식
이다. 그외 나머지는 deque()를 사용해서 쉽게 구현 할 수 있엇다.
-----------------------------------------------
의외로 방향? 에 대해서는 큰 문제를 하지 않았다.
왜냐?
문제에서 우선순위에 따라 좌우상하 같은 조건도 주어지지 않았고,
공을 맞으면 방향이 반대로 바뀐다.. 그러면 일일히 사람들의 방향도 +2 를하거나 90도로 꺾어지는 부분에서 또 고려를 해야한다. 하지만 그런거 없이 오직 방향만 바뀌는거면..
내가 만약 배열에서 인덱스 0부터 끝까지를 머리~몸통~꼬리 라고 정한다면,
이걸 반대로 reverse() 해서 뒤집어 버리면, 꼬리~몸통~머리로 되는게 아닌가? 싶었다.
그래서 이걸 유의하고
move() 함수와 같이 이녀석들이 움직일때 4가 움직일 수 있는 방향인데
점화식을 활용해서 deque을 관리했다. 그다음 움직이는곳이 0,0 이라고 해보자.
0,1 0,2 1,2 2,2
라고 한다면, 먼저 (0,1) 를 temp_x,temp_y 에 저장하고
0,2 1,2 2,2 2,2
이런식으로 <- 한칸씩 옮겨 준다.
그다음 맨 앞에 deque 의 appendleft()를 사용해서 temp값과 새로 움직여야하는 머리값을 차례대로 넣어준다.
0,1 0,2 1,2 2,2 2,2
-> temp_x,temp_y appendleft 하고
0,0 0,1 0,2 1,2 2,2 2,2
-> 새로 움직이는 좌표를 appendleft 해주고
마지막에 더미 데이터인 꼬리부분을 두번 pop 해서 지워주면,
0,0 0,1 0,2 1,2
와같이 팀들을 움직이게 할 수 있다.
팀들은 각 [deque(),deque()...] 이런식으로 구현했다.
먼저 전처리과정에서 2차원배열을 쭉 순회하며 maps[i][j] == 1 일때 팀을 하나 잡고 거기서부터 2 를 탐색 (bfs 사용) 하고 마지막에 3이나오면 탐색을 종료하며 그 탐색값을 deque()에 저장 했다.
여기서 문제였던게 만약에
2 1 3
2 0 2
2 2 2
이런식으로 되어있다면... 시작하자마자 3을 발견해서 팀이 0,1과 0,2 두개밖에 나오지 않게 된다.
그래서 이때 예외 처리를 했다.
처음 팀을 탐색할때, 첫 탐색에서 3이 나온다면, 그냥 무시하게 처리했다. 이거는 탐색할때마다 cnt 를 증가 시켜서
cnt가 1일때 3을 발견한다면 continue 해버리고, 나머지는 3을 만나면 거기서 종료시키게 처리했다.
생각외로 점화식에서 애먹었는데..
처음에 문제 조건에서 1부터 n 까지로 글이 나와있길래
글을 보면서 따라하기 쉽도록
라운드 수를 for tc in range(1,k+1) : 이렇게 처리했는데 ..
그덕에 그런지... 나중에
x % 4n -> 4n까지 끝나면 그다음 29는 다시 1번과 똑같아야한다.
이처리에서 뭔가 꼬이기 시작했다.
x % (4n+1) 을 해버리면 29가 0으로 나오는데, 여기서 +1을 해줘야한다.
근데 만약에 57이 온다고 치면, 28이 나오는데 28에서 +1을 더해버린다 (?) 그래서 else 문으로 빠져서 이상하게 처리되기 시작했다.
이걸 하나하나 예외식이나 점화식을 다시 세우기엔 너무 오래걸릴꺼같아서..
그냥
0~n-1
n~ 2*n-1
2*n ~ 3*n-1
3*n ~ 4n-1
이렇게 우리가 흔히 아는 0~n-1 처리로 바꿔버리고,
4n이 넘었을때 그냥 x%(4*n) 처리 해버리니까 귀찮게 +1 할필요도 없이 알아서 처리가 됐다.
이부분을 해결하고 실행하니 완료 할 수 있었다.
이번에는 한 4시부터 9시까지 조금 여유롭게? 풀었지만 하루내로 풀어서 기분이 좋다.
역시나 알고리즘 -> 문제에서 요구하는 조건을 어떤방식으로 구현할 것인가?
를 고려해서 풀었다.
모쪼록 6개월전에 비해 못풀던 문제를 풀게 되어서 기분이 좋다.
앞으로 코테까지 약 2주 남짓인데..
합격해서 코드트리에서 공부해서 합격했다고 떠벌떠벌 자랑하고싶다.
그도그럴게 백준이나 프로그래머스는 질문도와주는 선생님들이 없잖슴~~~~~~
|
from collections import deque
import sys
#sys.stdin = open("input.txt",'r')
n,m,k = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
deb = 0
dxs=[0,0,-1,1]
dys=[1,-1,0,0]
#각팀당 가지는 배열
team = [deque() for _ in range(m) ]
def in_range(x,y):
return 0<=x<n and 0<=y<n
#머리를 찾아야함
#초기전처리
head=0
for i in range(n) :
for j in range(n) :
if maps[i][j] == 1 :
#여기서 부터 dx,dy 진행하면서 머리와 꼬리를 찾아 나선다.
queue = deque()
visited = [ [False]*n for _ in range(n)]
visited[i][j] = True
queue.append((i,j))
team[head].append((i,j))
possible = False
cnt = 0
while queue :
cnt += 1
if possible :
break
x,y = queue.popleft()
#print(x,y)
for num in range(4) :
nx,ny = x+dxs[num],y+dys[num]
if in_range(nx,ny) and maps[nx][ny] == 2 and visited[nx][ny] == False:
queue.append((nx,ny))
visited[nx][ny] = True
team[head].append((nx,ny))
elif in_range(nx,ny) and maps[nx][ny] == 3 and cnt == 1 :
continue
elif in_range(nx,ny) and maps[nx][ny] == 3 :
team[head].append((nx,ny))
visited[nx][ny] = True
possible = True
if deb:
for test_c in visited:
print(*test_c)
for test_x in team[head]:
print(*test_x)
head +=1
if deb:
print(head)
def update_team() :
global maps
for i in range(n) :
for j in range(n) :
if maps[i][j] > 0 and maps[i][j] < 4 :
maps[i][j] = 4 #전부다 빈공간으로 초기화
for level in range(len(team)) :
queues = team[level]
for que in range(len(queues)) :
x,y = queues[que]
if que == 0 :
maps[x][y] = 1
elif que == (len(queues)-1) :
maps[x][y] = 3
else :
maps[x][y] = 2
return
def move() :
for level in range(len(team)) :
queue = team[level]
temp_queue = queue.copy()
#앞만 보고 갈 수있게 처리해야한다.
x,y = queue.popleft() #머리부터 가져와
for i in range(4):
nx,ny = x+dxs[i],y+dys[i]
if in_range(nx,ny) and (maps[nx][ny] == 4 or maps[nx][ny] == 3 ) :
next_x,next_y = nx,ny
break
# 방향을 이제 찾았다.
# 덱 값을 한칸씩 옮겨주고 마지막 빼고 머리 붙이기
temp_x,temp_y = temp_queue[0]
for item in range(0,len(temp_queue)-1) :
temp_queue[item] = temp_queue[item+1]
temp_queue.pop()
temp_queue.pop()
temp_queue.appendleft((temp_x,temp_y))
temp_queue.appendleft((next_x,next_y))
if deb:
print(temp_queue)
team[level] = temp_queue.copy()
update_team()
if deb:
print(maps)
return
def if_hit(x,y) :
if in_range(x,y):
if 1<= maps[x][y] <= 3 :
return True
else :
return False
return False
def change(x,y) :
return_point = 0
for level in range(len(team)) :
queue = team[level]
if (x,y) in queue :
idx = queue.index((x,y))
return_point = (idx +1)**2 #부딫힌사람 몇번째
#이제 맞았으니 해당 큐 위치를 바꿔줘야한다.
queue.reverse()
update_team()
if deb:
print(queue)
#바꾸고 난다음에 바로 리턴해줘서 끝내야한다. 안그러면 계속 바꿈.
return return_point
return #에러나게 만듬
def throw(round) :
point = 0
#여기서 라운드는 0~n-1 까지 들어오는걸 유의.
if round >= 4*n :
round = round%(4*n) # 4n이 넘어도 계속 반복되게
if 0 <= round <= n-1 :
for j in range(n) :
if if_hit(round,j) : # 만약 맞았다면,
point += change(round,j)
return point
elif n <= round <= 2*n-1 :
round = round%(n)
for row in range(n-1,-1,-1) :
if if_hit(row,round) : # 만약 맞았다면,
point += change(row,round)
return point
elif (2*n) <= round <= 3*n-1 :
round = round%((2*n)) # 인덱스 처리.
round = (n-round-1)
for col in range(n-1,-1,-1) :
if if_hit(round,col) : # 만약 맞았다면,
point += change(round,col)
return point
else : # 3n+1 <= round <= 4n-1
round = round%(3*n)
round = (n-round-1)
for row in range(n) :
if if_hit(row,round) : # 만약 맞았다면,
point += change(row,round)
return point
return point
answer = 0
for round in range(k) :
#각팀이 머리사람 따라서 한칸 이동
move()
#공이 선을따라 던져진다. 몇포인트를 먹었는지 반환해야함.
answer += throw(round)
#print(answer)
print(answer)
|
'코딩 테스트' 카테고리의 다른 글
| [코드트리 챌린지] 2022 삼성 상반기 오전1번 코드트리 - 술래잡기 파이썬 (0) | 2023.10.05 |
|---|---|
| [코드트리 챌린지] 정수 사각형 최소 합 (1) | 2023.10.04 |
| [2022 삼성 코딩테스트 상반기 오후 2번] 코드트리 - 나무 박멸 파이썬 리뷰 (0) | 2023.09.27 |
| [코드트리 챌린지] 2022 삼성 하반기 오전1번 기출문제 싸움땅 - 파이썬 리뷰 (0) | 2023.09.25 |
| [코드트리] 서로 다른 숫자 = set() 의 사용처 공부 (0) | 2023.09.21 |