삼성 기출
문제 링크 :
https://www.acmicpc.net/problem/13460
내가 생각한 문제 풀이
[시도1]
문제 보고 최소 몇 번만에라는 조건과 이차원 배열을 보고 BFS임이 유추 가능했다.
bfs를 돌리면서
visited, queue를 [[red y좌표, red x좌표], [blue y좌표, blue x좌표]] 형태로 저장했고 while문을 돌면서 조건을 맞췄다.
그냥 일반적인 형태이기 때문에 코드를 남겨두는 편이 좋을 것 같다.
시간 / 결과 / 패착
[시도1]
결과 : 오답
패착 :
프로그래머스와 다르게 백준에서는 테스트케이스 몇개 중 몇점이 아니라 정오답만 나온다. 내가 주어진 테케를 돌렸을 때 반정도는 맞고 반정도는 틀렸다. 몇가지 문제들이 잇었는데,
1. 한 번에 한 칸만
구슬은 동시에 한 칸에 있을 수 없다는 조건을 고려하지 않았다. 이걸 고려하지 않은 원인은 예제를 완전히 다 시뮬레이션 해보지 않고 대충 해봐서 틀린 것 같다. 평소에 예제를 잘 활용하기로 했었는데 아무튼 이 부분을 수정하려고 했을 때 맨 처음 생각한 아이디어는 어떤 방향으로 움직이냐에 따라서 어떤 좌표가 처음에 먼저 있느냐로 4가지 상황을 if문으로 구분해서 구현하려고 했는데, 답들을 보니까 그냥 move한 칸 수 가 더 많은 쪽을 한 칸 덜 움직이면 된다고 했다. 이렇게 구현할 경우 상황들을 나눌 필요가 없다.
2. 2차원 배열의 x좌표와 y좌표
솔직히 짜잘하게 잘못된 부분이 너무 많아서 이것 때문에 틀린 게 확실하진 않지만 나의 코드에서는 x좌표와 y좌표를 반대로 적었다. 왜냐면 이차원 배열 자체가
[[a,b,c],
[1,2,3],
[ㄱ,ㄴ,ㄷ]]이런 형태라고 생각했을 때,
graph[1][2] = 3이다. 그럼 y를 먼저 고려하고 x를 고려하게 되는 것 아닌가 ?
그런데 대부분은 graph[x][y]라고 작성한다.
일단 잠정적인 결론으로는 좌표상의 xy를 생각하지 않고, 그냥 x,y의 이름만 빌려오는 것 같다.
3. depth count
depth count를 나는 반복문 끝에서 1씩 올려주는 방식으로 시도했는데 다른 해설 코드에서는 큐에 넣거나 visited에 적는 방식으로 따로 관리해주고 있음
= > 여기가 결정적인 오류 포인트다. 디버깅 돌려 보니까 몇 번째 depth임과 무관하게 계속 for문한바퀴 돌면 answer값이 1씩올라간다.
4. blue 구슬이 들어가는 경우
나는 blue구슬이 들어가더라도 red구슬이 먼저 들어가는 경우를 상정해 flag를 사용하였다. 그러나 모든 답지에는 blue구슬이 들어가는 경우 continue를 하도록 하고, while문이 끝나면 -1을 return 하도록 하였다. 이렇게 약간 바꾸니 실행 되었다.
이 부분에 대해서 설명하자면, 만약 파란 구슬이 구멍에 떨어진다면 이번 for문 턴은 그냥 넘어가게 되고, 혹시 같은 depth에 red 구슬이 들어갈 수 있는 경우를 탐색할 수 있게 된다.
파란 구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안됨 따라서 이 경우 무시
라고 주석에 적혀 있는데 이 부분은 아직 이해하지 못했다.
혹시 다른 부분에서 틀린게 있는지 확인하기 위해 디버깅을 시도했다.
충격적이지만 자동완성 오타 때문이었다
하지만 이걸 고치고도 과제에 나온 테케만 풀 수 있었고 나는 시간 상 원인을 그만 찾기로 했다.
문제 해설
코드
나의 오답 코드
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
arr = []
for i in range(n):
temp = []
string = sys.stdin.readline().strip()
for j in range(m):
if string[j] == 'R':
redplace = [i,j]
elif string[j] == 'B':
blueplace = [i, j]
elif string[j] == 'O':
holeplace = [i, j]
temp.append(string[j])
arr.append(temp)
#U D L R
move_y = [-1, 1, 0, 0]
move_x = [0, 0, -1, 1]
def check(node, dir):
y, x = node
# dir에 맞춰서 for문으로 U/L는 0이 될때까지 D/R는 n/m이 될때까지 확인해서 .이 있는 마지막 위치를 반환
count = 0
if dir == 0:
for k in range(y-1, -1, -1):
if arr[k][x] == 'O':
return 100
elif arr[k][x] == '#':
return count
else:
count += 1
if dir == 1:
for k in range(y+1, n, 1):
if arr[k][x] == 'O':
return 100
elif arr[k][x] == '#':
return count
else:
count += 1
if dir == 2:
for k in range(x-1, -1, -1):
if arr[y][k] == 'O':
return 100
elif arr[y][k] == '#':
return count
else:
count += 1
if dir == 3:
for k in range(x+1, m, 1):
if arr[y][k] == 'O':
return 100
if arr[y][k] == '#':
return count
else:
count += 1
# 최단 거리를 찾아야 하니까 .. bfs로 이동 ?
def bfs(red, blue): # 시작 좌표 (Red와 Blue의)
answer = 1
visited = []
queue = deque([])
queue.append([red, blue])
while queue:
if answer >= 11:
return -1
rednode, bluenode = queue.popleft()
if [rednode, bluenode] not in visited:
visited.append([rednode, bluenode])
flag = False
for i in range(4):
# 여기서 만약에 안막혀있으면 쭉 이동해야 : 새로운 함수에서 movecount 몇 칸 움직일지 체크
redmove = check(rednode, i)
bluemove = check(bluenode, i)
if bluemove == 100:
flag = True
elif redmove == 100:
return answer
else:
new_red_y = rednode[0] + redmove * move_y[i]
new_red_x = rednode[1] + redmove * move_x[i]
new_blue_y = bluenode[0] + bluemove * move_y[i]
new_blue_x = bluenode[1] + bluemove * move_x[i]
if new_red_y == new_blue_y and new_red_x == new_red_x:
if redmove > bluemove: # 더 작은 값은 한 칸 덜 움직여야 한다
new_red_y -= move_y[i]
new_red_x -= move_x[i]
elif redmove < bluemove:
new_blue_y -= move_y[i]
new_blue_x -= move_x[i]
queue.append([[new_red_y, new_red_x],[new_blue_y,new_blue_x]])
answer += 1
if flag == True:
return -1
print(bfs(redplace, blueplace))나의 정답 코드
# 백준 구슬탈출 2
# 삼성
# 7:18 -
# 오답 이유 : 한 번에 한 칸만 : 동시에 있을 수는 없다는 조건 구현 안함
# 즉 예제를 완전히 다 시뮬레이션 안해보고 대충해봐서 틀린
# 이 부분 구현하려면 그 방향 쪽에서 더 앞에있는 구슬을 찾고(그 방향 한정 한 라인에 있다면) 그것부터 시행
# 자꾸 일부만 맞추는 이유 : 특정 부분을 구현하지 않음(빼먹는 부분이 있음)
# 이 문제에서 킥 : 미리 어떤 조건을 줘서 케이스를 나눠서 두 구슬이 한 곳에 있게 되면 누구를 땡기는게 아니라 더 많이 이동한 쪽을 한칸 빠꾸시키면 된
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
arr = []
for i in range(n):
temp = []
string = sys.stdin.readline().strip()
for j in range(m):
if string[j] == 'R':
redplace = [i,j]
elif string[j] == 'B':
blueplace = [i, j]
elif string[j] == 'O':
holeplace = [i, j]
temp.append(string[j])
arr.append(temp)
#U D L R
move_y = [-1, 1, 0, 0]
move_x = [0, 0, -1, 1]
def check(node, dir):
y, x = node
# dir에 맞춰서 for문으로 U/L는 0이 될때까지 D/R는 n/m이 될때까지 확인해서 .이 있는 마지막 위치를 반환
count = 0
if dir == 0:
for k in range(y-1, -1, -1):
if arr[k][x] == 'O':
return 100
elif arr[k][x] == '#':
return count
else:
count += 1
if dir == 1:
for k in range(y+1, n, 1):
if arr[k][x] == 'O':
return 100
elif arr[k][x] == '#':
return count
else:
count += 1
if dir == 2:
for k in range(x-1, -1, -1):
if arr[y][k] == 'O':
return 100
elif arr[y][k] == '#':
return count
else:
count += 1
if dir == 3:
for k in range(x+1, m, 1):
if arr[y][k] == 'O':
return 100
if arr[y][k] == '#':
return count
else:
count += 1
# 최단 거리를 찾아야 하니까 .. bfs로 이동 ?
def bfs(red, blue): # 시작 좌표 (Red와 Blue의)
visited = []
queue = deque([])
queue.append([red, blue, 1])
while queue:
rednode, bluenode, depth = queue.popleft()
if depth >= 11:
return -1
if [rednode, bluenode] not in visited:
visited.append([rednode, bluenode])
flag = False
for i in range(4):
# 여기서 만약에 안막혀있으면 쭉 이동해야 : 새로운 함수에서 movecount 몇 칸 움직일지 체크
redmove = check(rednode, i)
bluemove = check(bluenode, i)
if bluemove == 100:
continue
elif redmove == 100:
return depth
else:
new_red_y = rednode[0] + redmove * move_y[i]
new_red_x = rednode[1] + redmove * move_x[i]
new_blue_y = bluenode[0] + bluemove * move_y[i]
new_blue_x = bluenode[1] + bluemove * move_x[i]
if new_red_y == new_blue_y and new_red_x == new_blue_x:
if redmove > bluemove: # 더 작은 값은 한 칸 덜 움직여야 한다
new_red_y -= move_y[i]
new_red_x -= move_x[i]
elif redmove < bluemove:
new_blue_y -= move_y[i]
new_blue_x -= move_x[i]
queue.append([[new_red_y, new_red_x],[new_blue_y,new_blue_x], depth+1])
return -1
print(bfs(redplace, blueplace))추가 공부
BFS : depth 계산할 때 큐에 받아줘야 한다는 것
그냥 반복문 끝날때마다 단순히 1씩 올리면 안된다
큐에다가 depth를 박아 놔야 한다.
이차원 배열 : x좌표와 y좌표
그냥 상식적으로
tip for me
문제 풀고 해답 보는 과정에서 너무 난감했던 문제
문제를 어떻게 푸는지 알고, 알고리즘도 대략 맞았는데 부분부분 오류가 있었다.
여태껏 테스트케이스의 일부만 맞추는 것 때문에 좀 고민을 했었는데 그 원인을 제대로 알게 되었다. 모든 부분을 다 생각하지 않고 약간 단편적으로 문제를 푸는 경향이 있는 것 같다.
조건이나 특이한 부분을 메모해서 기록 해두고,
이 알고리즘이 모든 상황에 들어맞을지 한 번 생각해보고 코드를 짜는 게 좋을 것 같다.
그리고 알고 있다고 생각했던 기본적인 알고리즘 BFS DFS 크루스칼 다익스트라 등 을 좀 더 제대로 알 필요가 있다. 또 배열도..
대략 맞추는 것을 넘어서 모든 부분에서 문제가 없도록 해야 할 듯
화이팅
