2023년 8월 12일 알고리즘 문제풀이
문제 1 백준 18352
1차 시도
나의 생각
도시까지의 최단거리만 생각해야 하므로, bfs를 통해 도착한 도시에 얼마나 걸렸는지를 표시하고, 이를 방문표시로 이용하면 되겠다는 생각을 했다. 출발한 도시 와 도착지가 같을때는 0으로 표시하게 되는데, 이것 때문에 아직 방문처리하지 않은 것으로 취급되어 여러가지로 헷갈렸다. 따라서 제자리 거리를 1로 표시하여 모든 도시의 거리를 구하고 모두 1 만큼 감소시켜주었다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import sys
from collections import deque
n, m, k, x = map(int, sys.stdin.readline().split())
graph = [[]for _ in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
ans = []
visited = [0 for _ in range(n+1)]
def bfs(s):
visited[s] = 1
arr = deque()
arr.append(s)
while arr:
now = arr.popleft()
for next in graph[now]:
if not visited[next]:
arr.append(next)
visited[next] = visited[now]+1
bfs(x)
ans = []
if k == 0:
print(x)
else:
for i in range(1, n+1):
visited[i] -= 1
if i == x:
continue
if visited[i] == k:
print(i)
ans.append(i)
if not ans:
print(-1)
문제 2 백준 2178
1차 시도
나의 생각
위 문제와 결이 비슷하다고 생각했다. 갈 수있는 조건을 나타내는 graph에 거리를 더해서 표시하도록 하였다. 행렬 좌표와 index 값의 차이가 있으니 -1 해주는 것에 신경썼다. 또한 입력값을 받을 때 str로 받았으니 비교할 때도 1이 아닌 ‘1’로 비교하였다. 이 조건들만 유의한채 bfs를 이용하여 풀었다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = []
for _ in range(n):
tmp = list(sys.stdin.readline().rstrip())
graph.append(tmp)
dx = [0,-1,0,1]
dy = [1,0,-1,0]
def bfs(n,m):
arr = deque()
arr.append([0,0])
while arr:
x,y = arr.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx <= n-1 and ny >= 0 and ny <= m-1 and graph[nx][ny] == '1':
arr.append([nx,ny])
graph[nx][ny] = int(graph[x][y]) + 1
if nx == n-1 and ny == m-1:
return
bfs(n,m)
print(graph[n-1][m-1])
문제 3 백준 3061
1차 시도
나의 생각
사다리를 통해 두 도착 지점의 위치가 바뀐다고 생각하였다. 주어진 예시에서 2와 3사이의 사다리를 통해 [1,2,3]과 [3,1,2]가 연결되어 있는 상황에서 [1,2,3]과 [3,2,1]로 바뀌는 것이다. 하지만 도착지를 기준으로 어떤 사다리가 밑에 오는지를 결정하지 못했다. 이부분에 대해 더 생각해야 정답을 낼 수 있을것 같다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
ans = [0 for _ in range(n)]
while 0 in ans:
for i in range(n):
if arr[i] == i+1:
ans[i] = i+1
else:
tmp = arr[i]
while True:
if tmp == arr[i+1]:
break
if tmp > arr[i+1]:
arr[i] = arr[i+1]
arr[i+1] = tmp
i += 1
cnt += 1
elif tmp < arr[i+1]:
arr[i] = arr[i-1]
arr[i-1] = tmp
i -= 1
cnt += 1
print(cnt)
2차 시도
나의 생각
사다리가 생성되면 두 출발지가 연결되어 있는 도착지가 교환된다는 생각은 그대로 유지하였다. 다만 우선적으로 바꿔야 할 것을 왼쪽이나 오른쪽 위치로 생각하지 않고 작은 수인 1부터 위치를 확정짓도록 로직을 변경했다.
도착지의 순서를 배열이라 했을때 출발지는 index의 1을 더한값이다. 예시에서 1번에서 출발하면 3번, 2번에서 출발하면 1번, 3번에서 출발하면 2번에 도착한다. 즉 도착지 배열 arr은 [3,1,2] 로 설정한다. 3의 index는 0이므로 1을 더한 1이 출발지인 것이다. 희원이가 원하는 바는 도착지가 순서대로 [1,2,3]이 되는 방법이다. 즉 출발지 1의 도착지가 1이므로 값이 1인 index는 0, 출발지 2의 도착지가 2이므로 값이 2인 index는 1 과 같은 규칙이 성립해야한다.
도착지가 target인것을 탐색하였다. target의 출발지도 target이어야 하고 index는 target-1이어야 한다. 따라서 target-1 과 index를 비교하여 index 가 더 크면 왼쪽과 값을 바꿔주었다. 반대로 index가 더 작으면 오른쪽과 값을 바꿔주었다. 즉 index가 1이 작아지거나, 커지는 것이다. 이를 index = target-1이 성립할때까지 반복하였다.
값이 target인 index를 찾을때 target-1 부터 탐색하도록 하였다. 그 이전은 이미 정렬이 완료되었기 때문이다. 예를 들어 내가 값이 3인 곳을 찾는다는 것은 이전 loop에서 1,2를 알맞은 위치로 정렬했다는 의미이기 때문에 탐색할 필요가 없다.
생각보다 복잡하여 예시를 하나 더 들어 설명하겠다.
예시: 4-5-1-3-2 가 주어졌을때
현재 사다리에 가로선은 없는 상태로 1번에서 출발하면 4번 도착지, 2번에서 출발하면 5번 도착지, 3번에서 출발하면 1번 도착지, 4번에서 출발하면 3번 도착지, 5번에서 출발하면 2번 도착지에 도착한다. 이를 간단히 [4,5,1,3,2]로 표현하겠다. 도착지의 index는 출발지에서 1을 뺸 값이 된다. 4번 도착지의 출발지는? index가 0이므로 1을 더하면 된다. 그러면 출발지가 1임을 알 수 있다. 3번 도착지는? index 3에서 1을 더하면 4가 된다. 따라서 3번 도착지의 출발지는 4번이다.
4번 출발지와 5번 출발지의 세로줄에 가로 줄을 하나 긋는다면? 4번에서 출발하면 기존의 3번이 아니라 2번에 도착한다. 5번에서 출발하면 기존의 2번이 아니라 3번으로 도착한다. 따라서 [4,5,1,3,2]에서 [4,5,1,2,3]으로 수정된다. 이 상황에서, 희원이가 원하는 것은 1번을 출발하면 1번 도착지, 5번을 출발하면 5번 도착지에 도달하는 것이다. 즉 [1,2,3,4,5] 처럼 오름차순 정렬이 되길 바라는 것이다. 단, 교환을 최대한 적게 하는 조건에서.
나의 로직은 1번부터 제자리를 찾아가는 것이다. target을 1로 잡는다. [4,5,1,3,2]에서 1번 도착지의 출발지는 3번이다. idx는 2다. 1번 도착지의 출발지는 1이어야 하고, index값은 0이어야 한다. index = target-1 이므로 target-1과 idx를 비교한다. idx가 더 크니 줄여야 한다. 이를 줄이기 위해 왼쪽으로 이동한다. 따라서 index가 1인 원소와 값을 교환하고, idx는 1이 된다. 배열은 [4,1,5,3,2] 가 된다. 교환이 한번 일어났으므로 cnt 는 1이 된다. cnt는 교환 횟수이자 가로줄을 의미한다.
이를 한번 더하면 [1,4,5,3,2]가 된다. 맨 앞의 1은 더이상 탐색할 의미가 없다. 이제 target을 2로 잡고 위를 반복한다. target은 1부터 4까지만 순회한다. 4개가 정렬이 완료되면 5번째는 볼 의미가 없기 때문이다.
1부터 하는 이유? 사다리를 1번부터 타게 되니까! 1번이 도착한 이후 1번에 영향을 끼치지 않도록 점차 더 위에 가로줄을 그리게 된다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
for target in range(1,n):
for i in range(target-1,n):
if arr[i] == target:
idx = i
break
while idx != target-1:
cnt += 1
if idx > target-1:
tmp = arr[idx-1]
arr[idx-1] = target
arr[idx] = tmp
idx -= 1
else:
tmp = arr[idx+1]
arr[idx+1] = target
arr[idx] = tmp
idx += 1
print(cnt)
