★구슬 탈출★
★다시 풀어봐야할 문제★(구현 3시간 걸렸고, 코너케이스 많아서 굉장히 복잡한 문제, 코드도 엄청 지저분해서 다음에 풀때는 깔끔한 코드로 풀어보기)
접근 방법 [필수 작성]
제한 조건 확인
네가지 동작(상하좌우)
기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
가장 바깥 행과 열은 모두 막혀져 있고
보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
- 보드 크기 최대 10x10
두개 동시에 들어가는 경우
10 번 이내로 못넣는 경우
R이랑 B랑 겹쳐있을때 처리가 까다로울 수 있음
누구를 먼저 옮기냐에 따라서 막혔냐 뚫렸냐가 달라질 수 있음
구슬 움직이는 함수 실행시키기 전에
R이랑 B랑 같은 열이나 행에 위치하는지 확인하고,
만약 같은 열이나 행에 위치하면 누구 먼저 옮길지 결정해주고 옮긴다.
R과 B가 같은 열에 있다면
→ 상방행이동을 할때는 더 위쪽에 있는애를 먼저 옮긴다.
→ 하방행이동을 할때는 더 아래쪽에 있는애를 먼저 옮긴다.
R과 B가 같은 행에 있다면
→ 오른열이동을 할때는 더 오른쪽에 있는애를 먼저 옮긴다.
→ 왼쪽열이동을 할때는 더 왼쪽에 있는애를 먼저 옮긴다.
아이디어
DFS 활용할 것임 (BFS 도 활용할 수 있는지 나중에 생각해보기)
DFS 를 활용하는 이유는 R을 움직일 수 있는 경우의 수가 각 단계별로 생길때마다 해당 보드의 모습을 다음 재귀로 넘겨줘야하기 때문
구슬은 항상 어느상황이든 막힐때까지 간다고 했으므로 한쪽 벽은 막혀있음
한 번 진행시마다 몇번 구슬을 옮겼는지 카운팅
B는 A의 움직임에 종속됨 → 즉, A는 안움직이고 B 혼자 움직이는 경우는 없음 → 그렇게 움직이는건 의미가 없기 때문
R이 움직일 수 있는 모든 가능한 방향으로 DFS 를 진행
움직인 결과에 count ++ 하고, 다음 재귀 루프 진행,
만약 count 가 10인데도 구멍에 못들어갔으면 return 해서 빠져나옴
중력에 의해 끝까지 움직이는 함수를 하나 만듬
만약 앞에 벽이 아닌 다른 구슬에 의해 막혔을때는 다른 구슬을 먼저 움직이고 해당 구슬을 움직임
시간복잡도
R이 움직일수 있는 방향 가짓수 3
한번 움직일때 최대 움직이는 횟수 8 (10x10 보드이기때문)
8*(3^10) = 472,392 → 시간내 통과가능
자료구조
코드 구현 [필수 작성]
1차 시도 (2시간)
코드 반복되는 부분 많고, 가독성 똥망
테케 7번 빼고 다 통과되서 한번 백업
테케 7번 안되는 이유는 구슬 움직일때 R,B 선후관계 따질때 board 가 업데이트가 안된 상태로 기존 보드에서 구슬을 움직여서 그럼.
R 움직이자마자 B도 그 사실을 알 수 있게 만들어줘야함. 그리고 구멍에 들어갔을땐 O 를 R 로 업데이트하는게 아니라 그냥 R 을 보드에서 삭제해야함.
import copy
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
def is_valid_move(R_r,R_c,i,tmp_board):
global dr,dc
if tmp_board[R_r + dr[i]][R_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(tmp_board,ball_index,dr,dc):
global N,M
nr = ball_index[0] + dr
nc = ball_index[1] + dc
while True:
if tmp_board[nr][nc] == ".":
nr += dr
nc += dc
elif tmp_board[nr][nc] == "O":
break
else:
nr -= dr
nc -= dc
break
return (nr,nc)
def goal_in(count,tmp_board,R_index,B_index,O_index): #count 는 현재 몇번째 진행중인지, flag 는 빨간공이 골인 됐는지
global flag
R_r,R_c = R_index
B_r,B_c = B_index
O_r,O_c = O_index
print("hello")
if flag == 1:
return
if count > 10:
return
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
for i in range(4):
print("hello2")
if is_valid_move(R_r,R_c,i,tmp_board):
if R_r == B_r: #행이 같을때
if i == 0: #오른열이동일때는 더 오른쪽놈 먼저
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
elif i == 2: #왼쪽열 이동일때는 더 왼쪽좀 먼저
print("왼쪽열이동")
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
else:
print("레드먼저")
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
elif R_c == B_c: #열이 같을때
if i == 1: #하방행이동일때는 더 아래쪽놈을 먼저 이동
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
elif i == 3: #상방행이동일때는 더 위쪽놈을 먼저 이동
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
else: #행도 열도 같지 않을땐 뭘 먼저 이동해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
# 여기까지 구슬 이동이 끝나고 새로운 구슬 index 가 업데이트 됨
print(R_r,R_c)
print(B_r,B_c)
if R_r == O_r and R_c == O_c:
if B_r == O_r and B_c == O_c:
# 다음 for 루프를 위해 인덱스 초기화
print("hi!!!!")
R_r,R_c = R_index
B_r,B_c = B_index
continue
else:
flag = 1
return
# 보드에서 구슬 이동
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
#재귀호출
goal_in(count+1,tmp_board,(R_r,R_c),(B_r,B_c),O_index) #tmp_board의 복사본을 넣어야하나? -> 원본하나로 돌려막기 할 수 있지 않을까?
# 보드 구슬 원위치
tmp_board[R_r][R_c] = "."
tmp_board[R_index[0]][R_index[1]] = "R"
tmp_board[B_r][B_c] = "."
tmp_board[B_index[0]][B_index[1]] = "B"
# 다음 for 루프를 위해 인덱스 초기화
R_r,R_c = R_index
B_r,B_c = B_index
goal_in(0,board,R_index,B_index,O_index)
print(flag)2차 시도
제출 7% 에서 틀려서 못넘어가는중…
반례 생각중…
근데 코드가 너무 더럽다 ㅠㅠ
import copy
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
def is_valid_move(R_r,R_c,i,tmp_board):
global dr,dc
if tmp_board[R_r + dr[i]][R_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(tmp_board,ball_index,dr,dc):
global N,M
nr = ball_index[0] + dr
nc = ball_index[1] + dc
while True:
if tmp_board[nr][nc] == ".":
nr += dr
nc += dc
elif tmp_board[nr][nc] == "O":
break
else:
nr -= dr
nc -= dc
break
return (nr,nc)
def goal_in(count,tmp_board,R_index,B_index,O_index): #count 는 현재 몇번째 진행중인지, flag 는 빨간공이 골인 됐는지
global flag
R_r,R_c = R_index
B_r,B_c = B_index
O_r,O_c = O_index
#print("hello")
if flag == 1:
return
if count > 10:
return
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
for i in range(4):
#print("hello2")
if is_valid_move(R_r,R_c,i,tmp_board):
if R_r == B_r: #행이 같을때
if i == 0: #오른열이동일때는 더 오른쪽놈 먼저
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
elif i == 2: #왼쪽열 이동일때는 더 왼쪽좀 먼저
#print("왼쪽열이동")
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
#print("레드먼저")
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
elif R_c == B_c: #열이 같을때
if i == 1: #하방행이동일때는 더 아래쪽놈을 먼저 이동
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
elif i == 3: #상방행이동일때는 더 위쪽놈을 먼저 이동
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else: #행도 열도 같지 않을땐 뭘 먼저 이동해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
# 여기까지 구슬 이동이 끝나고 새로운 구슬 index 가 업데이트 됨
#print(R_r,R_c)
#print(B_r,B_c)
if R_r == O_r and R_c == O_c:
if B_r == O_r and B_c == O_c:
# 다음 for 루프를 위해 인덱스 초기화
#print("hi!!!!")
R_r,R_c = R_index
B_r,B_c = B_index
continue
else:
flag = 1
return
# 보드에서 구슬 이동
# if R_r == O_r and R_c == O_c:
# tmp_board[R_index[0]][R_index[1]] = "."
# else:
# tmp_board[R_index[0]][R_index[1]] = "."
# tmp_board[R_r][R_c] = "R"
# if B_r == O_r and B_c == O_c:
# tmp_board[B_index[0]][B_index[1]] = "."
# else:
# tmp_board[B_index[0]][B_index[1]] = "."
# tmp_board[B_r][B_c] = "B"
#재귀호출
goal_in(count+1,tmp_board,(R_r,R_c),(B_r,B_c),O_index) #tmp_board의 복사본을 넣어야하나? -> 원본하나로 돌려막기 할 수 있지 않을까?
# 보드 구슬 원위치
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "R"
else:
tmp_board[R_r][R_c] = "."
tmp_board[R_index[0]][R_index[1]] = "R"
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "B"
else:
tmp_board[B_r][B_c] = "."
tmp_board[B_index[0]][B_index[1]] = "B"
# 다음 for 루프를 위해 인덱스 초기화
R_r,R_c = R_index
B_r,B_c = B_index
goal_in(0,board,R_index,B_index,O_index)
print(flag)3차 시도
if B_r == O_r and B_c == O_c:
R_r,R_c = R_index
B_r,B_c = B_index
continue
else:
if R_r == O_r and R_c == O_c:
flag = 1
return파랑구슬이 구멍에 들어간 걸 체크해주는 순서를 바꿔줬음 → 그랬더니 7% 에서 23%까지 올라감
반례 모르겠어서 반례 찾아봄
[반례]
7 7
#######
#...O.#
#.....#
#.....#
#.B...#
#..R..#
#######
정답: 0
출력: 1
import copy
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
def is_valid_move(R_r,R_c,i,tmp_board):
global dr,dc
if tmp_board[R_r + dr[i]][R_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(tmp_board,ball_index,dr,dc):
global N,M
nr = ball_index[0] + dr
nc = ball_index[1] + dc
while True:
if tmp_board[nr][nc] == ".":
nr += dr
nc += dc
elif tmp_board[nr][nc] == "O":
break
else:
nr -= dr
nc -= dc
break
return (nr,nc)
def goal_in(count,tmp_board,R_index,B_index,O_index): #count 는 현재 몇번째 진행중인지, flag 는 빨간공이 골인 됐는지
global flag
R_r,R_c = R_index
B_r,B_c = B_index
O_r,O_c = O_index
#print("hello")
if flag == 1:
return
if count > 10:
return
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
for i in range(4):
#print("hello2")
if is_valid_move(R_r,R_c,i,tmp_board):
if R_r == B_r: #행이 같을때
if i == 0: #오른열이동일때는 더 오른쪽놈 먼저
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
elif i == 2: #왼쪽열 이동일때는 더 왼쪽좀 먼저
#print("왼쪽열이동")
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
#print("레드먼저")
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
elif R_c == B_c: #열이 같을때
if i == 1: #하방행이동일때는 더 아래쪽놈을 먼저 이동
if B_r > R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
elif i == 3: #상방행이동일때는 더 위쪽놈을 먼저 이동
if B_r < R_r:
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else:
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
else: #그게 아닐땐 뭘해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
else: #행도 열도 같지 않을땐 뭘 먼저 이동해도 상관없음
B_r,B_c = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "."
else:
tmp_board[B_index[0]][B_index[1]] = "."
tmp_board[B_r][B_c] = "B"
R_r,R_c = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "."
else:
tmp_board[R_index[0]][R_index[1]] = "."
tmp_board[R_r][R_c] = "R"
# 여기까지 구슬 이동이 끝나고 새로운 구슬 index 가 업데이트 됨
#print(R_r,R_c)
#print(B_r,B_c)
if B_r == O_r and B_c == O_c:
R_r,R_c = R_index
B_r,B_c = B_index
continue
else:
if R_r == O_r and R_c == O_c:
flag = 1
return
# 보드에서 구슬 이동
# if R_r == O_r and R_c == O_c:
# tmp_board[R_index[0]][R_index[1]] = "."
# else:
# tmp_board[R_index[0]][R_index[1]] = "."
# tmp_board[R_r][R_c] = "R"
# if B_r == O_r and B_c == O_c:
# tmp_board[B_index[0]][B_index[1]] = "."
# else:
# tmp_board[B_index[0]][B_index[1]] = "."
# tmp_board[B_r][B_c] = "B"
#재귀호출
goal_in(count+1,tmp_board,(R_r,R_c),(B_r,B_c),O_index) #tmp_board의 복사본을 넣어야하나? -> 원본하나로 돌려막기 할 수 있지 않을까?
# 보드 구슬 원위치
if R_r == O_r and R_c == O_c:
tmp_board[R_index[0]][R_index[1]] = "R"
else:
tmp_board[R_r][R_c] = "."
tmp_board[R_index[0]][R_index[1]] = "R"
if B_r == O_r and B_c == O_c:
tmp_board[B_index[0]][B_index[1]] = "B"
else:
tmp_board[B_r][B_c] = "."
tmp_board[B_index[0]][B_index[1]] = "B"
# 다음 for 루프를 위해 인덱스 초기화
R_r,R_c = R_index
B_r,B_c = B_index
goal_in(0,board,R_index,B_index,O_index)
print(flag)4차 시도
구슬이 겹친 케이스 때문에 하드코딩으로 케이스분류를 해주어서 코드가 반복되는 부분이 굉장히 많아짐.
다음의 로직을 적용하여 코드를 수정.
이번에는 29% 에서 실패..
또 다른 반례 있는듯..
반례 만들어보기
3 5
#####
#ROB#
#####
정답: 1
3 5
#####
#RBO#
#####
정답: 0
3 5
#####
#BRO#
#####
정답: 0if 구슬이 겹친 경우:
if R 이동 횟수 > B 이동 횟수:
R을 한칸 뒤로
else:
B를 한칸 뒤로import copy
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
def is_valid_move(R_r,R_c,i,tmp_board):
global dr,dc
if tmp_board[R_r + dr[i]][R_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(tmp_board,ball_index,dr,dc):
global N,M
moved_pixel = 0
nr = ball_index[0] + dr
nc = ball_index[1] + dc
moved_pixel += 1
while True:
if tmp_board[nr][nc] == "O":
break
elif tmp_board[nr][nc] == "#":
nr -= dr
nc -= dc
moved_pixel -= 1
break
else:
nr += dr
nc += dc
moved_pixel += 1
return (nr,nc,moved_pixel)
def goal_in(count,tmp_board,R_index,B_index,O_index): #count 는 현재 몇번째 진행중인지, flag 는 빨간공이 골인 됐는지
global flag
R_r,R_c = R_index
B_r,B_c = B_index
O_r,O_c = O_index
if flag == 1:
return
if count > 10:
return
for i in range(4):
if is_valid_move(R_r,R_c,i,tmp_board):
new_R_r,new_R_c,R_moved_count = move_ball_to(tmp_board,(R_r,R_c),dr[i],dc[i])
new_B_r,new_B_c,B_moved_count = move_ball_to(tmp_board,(B_r,B_c),dr[i],dc[i])
#print((new_R_r,new_R_c),(new_B_r,new_B_c))
if (new_B_r,new_B_c) == O_index:
continue
else:
if (new_R_r,new_R_c) == O_index:
flag = 1
return
if (new_R_r,new_R_c) == (new_B_r,new_B_c):
if R_moved_count > B_moved_count:
new_R_r -= dr[i]
new_R_c -= dc[i]
else:
new_B_r -= dr[i]
new_B_c -= dc[i]
# 여기까지 구슬 index 업데이트 완료
# 이제 변화된 구슬 인덱스에 맞게 board 업데이트 해야됨
tmp_board[new_R_r][new_R_c] = "R"
tmp_board[R_r][R_c] = "."
tmp_board[new_B_r][new_B_c] = "B"
tmp_board[B_r][B_c] = "."
goal_in(count+1,tmp_board,(new_R_r,new_R_c),(new_B_r,new_B_c),O_index)
tmp_board[new_R_r][new_R_c] = "."
tmp_board[R_r][R_c] = "R"
tmp_board[new_B_r][new_B_c] = "."
tmp_board[B_r][B_c] = "R"
goal_in(0,board,R_index,B_index,O_index)
print(flag)5차 시도
이번엔 BFS 로 구현해봤음
동일하게 29%에서 틀림
뭔가 내 코드나 로직에 오류가 있는듯…
import copy
from collections import deque
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
visited = set()
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
board[R_index[0]][R_index[1]] = "."
board[B_index[0]][B_index[1]] = "."
def is_valid_move(R_r,R_c,i):
global dr,dc,board
if board[R_r + dr[i]][R_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(ball_index,dr,dc):
global N,M,board
moved_pixel = 0
nr = ball_index[0] + dr
nc = ball_index[1] + dc
moved_pixel += 1
while True:
if board[nr][nc] == "O":
break
elif board[nr][nc] == "#":
nr -= dr
nc -= dc
moved_pixel -= 1
break
else:
nr += dr
nc += dc
moved_pixel += 1
return (nr,nc),moved_pixel
q = deque([((R_index,B_index),0)]) # ((R,B),count)
visited.add((R_index,B_index))
while q:
if flag == 1:
break
RB, count = q.popleft()
tmp_R_index, tmp_B_index = RB
if count > 10:
break
for i in range(4):
if is_valid_move(tmp_R_index[0],tmp_R_index[1],i):
new_R_index, R_moved_count = move_ball_to(tmp_R_index,dr[i],dc[i])
new_B_index, B_moved_count= move_ball_to(tmp_B_index,dr[i],dc[i])
if new_B_index == O_index:
continue
else:
if new_R_index == O_index:
flag = 1
break
if new_R_index == new_B_index:
if R_moved_count > B_moved_count:
new_R_index = (new_R_index[0]-dr[i],new_R_index[1]-dc[i])
else:
new_B_index = (new_B_index[0]-dr[i],new_B_index[1]-dc[i])
if (new_R_index,new_B_index) not in visited:
q.append(((new_R_index,new_B_index),count+1))
visited.add((new_R_index,new_B_index))
print(flag)6차 시도
Q4에 따라 코드를 직접 수정
import copy
from collections import deque
N, M = map(int,input().split()) # N 은 row, M 은 col
board = []
for _ in range(N):
list = []
string = input()
for s in string:
list.append(s)
board.append(list)
dr = [0,1,0,-1]
dc = [1,0,-1,0]
# 0 = 오른열이동, 1 = 하방행이동, 2 = 왼쪽열이동, 3 = 상방행이동
flag = 0
visited = set()
for r in range(N):
for c in range(M):
if board[r][c] == "R":
R_index = (r,c)
elif board[r][c] == "B":
B_index = (r,c)
elif board[r][c] == "O":
O_index = (r,c)
board[R_index[0]][R_index[1]] = "."
board[B_index[0]][B_index[1]] = "."
def is_valid_move(R_r,R_c,B_r,B_c,i):
global dr,dc,board
if board[R_r + dr[i]][R_c + dc[i]] != "#" or board[B_r + dr[i]][B_c + dc[i]] != "#":
return True
else:
return False
def move_ball_to(ball_index,dr,dc):
global N,M,board
moved_pixel = 0
nr = ball_index[0] + dr
nc = ball_index[1] + dc
moved_pixel += 1
while True:
if board[nr][nc] == "O":
break
elif board[nr][nc] == "#":
nr -= dr
nc -= dc
moved_pixel -= 1
break
else:
nr += dr
nc += dc
moved_pixel += 1
return (nr,nc),moved_pixel
q = deque([((R_index,B_index),1)]) # ((R,B),count)
visited.add((R_index,B_index))
while q:
if flag == 1:
break
RB, count = q.popleft()
tmp_R_index, tmp_B_index = RB
if count > 10:
break
for i in range(4):
if is_valid_move(tmp_R_index[0],tmp_R_index[1],tmp_B_index[0],tmp_B_index[1],i):
new_R_index, R_moved_count = move_ball_to(tmp_R_index,dr[i],dc[i])
new_B_index, B_moved_count= move_ball_to(tmp_B_index,dr[i],dc[i])
if new_B_index == O_index:
continue
else:
if new_R_index == O_index:
flag = 1
break
if new_R_index == new_B_index:
if R_moved_count > B_moved_count:
new_R_index = (new_R_index[0]-dr[i],new_R_index[1]-dc[i])
else:
new_B_index = (new_B_index[0]-dr[i],new_B_index[1]-dc[i])
if (new_R_index,new_B_index) not in visited:
q.append(((new_R_index,new_B_index),count+1))
visited.add((new_R_index,new_B_index))
print(flag)
배우게 된 점 [ 필수 X ]
코너 케이스가 많아서 생각하기 굉장히 까다로운 문제
일정 횟수 내로 목표를 달성해야하는 문제의 경우
DFS가 아닌 BFS로 구현하면 좀 더 쉽게 접근이 가능할 것이다.
BFS 구현시 보드 업데이트 정보는 어떻게 넘겨주지?
→ R과 B 를 보드에서 지우고, 인덱스 정보만으로 가지고 놀기
문제에 대한 이해도 높히기
질문 [ 필수 X ]
Q1
코드가 반복되는 부분도 굉장히 많고.. 반복되는 부분을 함수로 빼려했는데 어려워서 그냥 더럽더라도 일단 풀어보자라는 마인드로 구현을 이어했는데.. 너무 복잡해서 길을 잃어버렸습니다..
저번에 양과 늑대도 비슷한 양상으로 이렇게 길을 잃었었는데.. 구현하다 점점 복잡해지면 다시 돌아갈수도 없고, 포기하고 다음문제로 넘어갈수도 없고, 어떻게 해야할지 모르겠습니다.
Q2
3차 시도의 반례에 대해서 디버깅 중에 board 를 프린트해보았는데, 예상치 못한 board 모양이 계속나와서 우선 멈춘 상태입니다… 코치님이 보셨을때.. 복구가 가능한 상황이면 팁을 주시고.. 아니라면 코드를 갈아엎는편이 더 빠를것같기도 합니다..
Q3 (추가질문)
A2 의 코치님 조언대로 코드를 수정하니 훨씬 간결해지고 가독성이 좋아졌습니다. 놀랍네요… 그런데 이전 반례들을 해결했지만 추가적인 반례가 있는것 같은데 반례를 못찾겠습니다… DFS,BFS 둘다 같은 로직으로 구현해봤는데 동일하게 29% 에서 틀리는 상황입니다.
제가 의심가는 부분은
5차시도 코드 중..
구슬이 구멍에 빠지는 경우와 구슬이 겹치는 경우를 처리하는 부분인 것 같은데 확실하지 않습니다..
이 문제에만 6시간을 투자해서 우선 다음문제로 넘어가겠습니다..
if new_B_index == O_index:
continue
else:
if new_R_index == O_index:
flag = 1
break
if new_R_index == new_B_index:
if R_moved_count > B_moved_count:
new_R_index = (new_R_index[0]-dr[i],new_R_index[1]-dc[i])
else:
new_B_index = (new_B_index[0]-dr[i],new_B_index[1]-dc[i])Q4
피드백 [ 코치 작성 ]
A1
길을 잃은 경우에는 빠르게 되돌아 가는 것이 더 좋습니다. 초기에 어떻게 로직을 구현할지를 명확하게 생각하고 구현하는 경우에는 길을 쉽게 잃지 않지만 로직이 모호해 코드 작성이 길어진 경우, 로직이 명확하더라도 코드 작성 시간이 길어지거나 불명확한 변수명 사용 등으로 인해 길을 잃은 경우 잠시 살펴본 후에도 길을 되찾아가지 못했다면 해당 지점까지 작성하며 떠올린 로직을 기반으로 처음부터 다시 작성하시는 것이 더욱 빠를 수 있습니다.
길을 잃지 않고자 처음부터 로직을 완벽하게 구상하고 코드를 작성하는 것 또한 시간을 오래 잡아먹을 수 있으니 적절한 균형을 두어 로직 구상과 작성에 밸런스를 맞추는 것이 좋습니다.
A2
구슬이 겹치는 경우를 고려하며 코드가 길어진 것 같습니다. 구슬이 겹치는 경우를 다음과 같이 처리해보시기 바랍니다
if 구슬이 겹친 경우:
if R 이동 횟수 > B 이동 횟수:
R을 한칸 뒤로
else:
B를 한칸 뒤로
어제보다 더, 내일보다 덜.