✅ BOJ IT 기업 문제 풀이
🎈 10431 줄세우기
다음 과정을 거쳐 오름차순 정렬을 한다.
- 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝남
- 자기 앞에 큰 학생이 1명 이상이라면 그 중 가장 앞에 있는 학생 바로 앞에 서고 그 뒤 모든 학생들은 뒤로 1발짝 이동한다.
입출력은 다음과 같다.- 입력 : 첫 줄에 테케 수 P가 주어지고 각 테케 별로 테케 번호와 20개의 양의 정수가 공백으로 주어진다.
- 출력 : 각 테케에 대해 테케 번호와 뒤로 물러난 걸음의 총합을 공백으로 구분해 출력한다.
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
line = list(map(int, input().rstrip().split()))
cnt = 0
# i인덱스 지정
for i in range(1, len(line)-1):
# i인덱스 뒤에 애들에 한해서
for j in range(i+1, len(line)):
# 앞에 애들이 더 크면 위치 바꾸고 +1
if line[i] > line[j]:
line[i], line[j] = line[j], line[i]
cnt += 1
print(line[0], cnt)
< 풀이 과정 >
단순 구현 문제 이런 방식은 dp예제 문제에서도 많이 볼 수 있다.
line으로 주어진 입력을 받고 1~(n-1)로 범위를 지정해둔다.
이후 j로 인덱스를 나타내는데 i보다 인덱스를 크게 해주기 위해 i+1부터 끝까지 범위를 지정한다.
이후 앞에 있는 사람이 뒷사람보다 값이 크면 변경하고 + 1 처리 후 리턴!
🎈 13460 구슬 탈출 2 (그래프 탐색)
구슬 탈출은 직사각형 보드에 빨간 구슬 ,파랑 구슬을 하나씩 넣은 다음 빨간 구슬을 구멍을 통해 빼내는 게임으로 목표는 빨간 구슬을 구멍을 통해 뺴내는 것이고 파란 구슬이 구멍에 들어가도록 해선 안된다. 구멍으로 빼내는 과정은 위, 아래, 오른쪽, 왼쪽으로 기울이는 방법으로 빨간 구슬, 파란 구슬은 동시에 같은 칸에 있을 수 없다. 위 과정을 거쳐 최소 몇 번만에 빨간 구슬을 빼내는 지 구하는 문제.
- 조건은 다음과 같다.
빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.입출력은 다음과 같다.
- 입력 : 첫 줄에 보드 세로, 가로를 의미하는 n, m이 주어지고 다음 n줄에 보드 모양을 나타내는 길이 m의 문자열이 주어진다. 문자열에서 .는 빈칸, #은 벽, O는 구멍 위치, R은 빨간 구슬 위치, B는 파란 구슬 위치이다. 입력되는 보드의 가장자리에는 모두 벽이 존재하고 구멍 개수, 빨간 구슬, 파란 구슬 개수는 항상 1개로 주어진다.
- 출력 : 빨간 구슬을 구멍으로 빼낼 수 있는 최소 횟수를 구하는 문제로 10번 이하로 움직여서 빨간 구슬을 뺄 수 없으면 -1을 출력한다.
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 빨간구슬, 파란구슬 위치 총 4번
visited = [[[[0]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
# 그래프 입력넣고 빨간구슬, 파란구슬 각 시작점 정하기
graph = [list(input().rstrip()) for _ in range(n)]
for i in range(n):
for j in range(m):
if graph[i][j] == 'R':
rx, ry = i, j
graph[i][j] = '.'
elif graph[i][j] == 'B':
bx, by = i, j
graph[i][j] = '.'
# 기울이는 순간 벽의 끝으로 이동하는 함수 생성
def move(x, y, dx, dy):
move_cnt = 0
while graph[x+dx][y+dy] != '#' and graph[x][y] != 'O':
x += dx
y += dy
move_cnt += 1
return x, y, move_cnt
def bfs():
queue = deque()
queue.append((rx, ry, bx, by, 1))
visited[rx][ry][bx][by] = 1
while queue:
red_x, red_y, blue_x, blue_y, cnt = queue.popleft()
# 구슬 이동이 10번 이상이면 중단
if cnt > 10:
break
# 각 구슬 별 상하좌우 탐색 진행
for i in range(4):
nrx, nry, rmove = move(red_x, red_y, dx[i], dy[i])
nbx, nby, bmove = move(blue_x, blue_y, dx[i], dy[i])
# 파란구슬이 구멍에 들어가지 않았다는 조건 하에
if graph[nbx][nby] != 'O':
# 빨간구슬이 구멍에 들어가면 벽 기울인 횟수 cnt 리턴
if graph[nrx][nry] == 'O':
return cnt
# 빨간구슬, 파란구슬 같은 위치인 경우
if nrx == nbx and nry == nby:
# 더 많이 기울인 구슬을 골라 해당 구슬의 위치를 이전으로 돌리기
if rmove > bmove:
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
# 방문하지 않았던 곳에 한해 queue에 삽입하고 방문처리
if not visited[nrx][nry][nbx][nby]:
visited[nrx][nry][nbx][nby] = 1
queue.append((nrx, nry, nbx, nby, cnt + 1))
return -1
print(bfs())< 풀이 과정 >
며칠 전 풀었지만 실패해 다시 도전하여 해결한 풀이 💯
핵심은 빨간 구슬, 파란 구슬의 시작점을 미리 정하고 벽을 한 칸씩 이동하는 것이 아닌 기울이기에 다음 위치가 벽인지 여부를 따지며 진행한다.
각 구현한 코드를 풀이하면 다음과 같다.
- n, m, graph, visited 변수를 각각 지정 후 빨간 구슬, 파란 구슬 위치를 지정해놓는다.
- move 함수를 통해 현 위치와 dx, dy로 방향을 매개변수로 입력받아 다음 위치가 벽이 아니고 현 위치가 구멍이 아닌 조건에 한해 기울인 것을 표현해준다.
- bfs 함수를 통해 현위치와 기울인 횟수를 큐에 넣어주고 빌 때까지 반복을 진행하며 pop한 다음 위치의 각 구슬을 다음 조건에 걸쳐 표현해주어야 한다.
무조건 파란구슬은 구멍에 들어가지 않아야 하므로, 파란 구슬의 다음위치를 구멍에 넣지 않는 조건에 한해 다음 위치에 빨간 구슬이 구멍에 들어간 순간 기울인 횟수 cnt를 리턴한다.
빨간 구슬과 파란 구슬은 같은 위치에 속할 수 없으므로 둘 중 기울인 횟수가 더 큰 쪽에 조건을 걸어 이전으로 돌린다.
마지막으로 방문하지 않은 곳에 한해 queue에 삽입하고 방문처리를 해준다.
위 조건을 걸어 빨간구슬만이 구멍에 들어가고, 총 기울인 횟수가 10회 미만인 경우에 한해 cnt가 리턴될 것이고 아닌 경우 -1이 리턴될 것이다.
