- 예제 입력 1 -
사람의 수 / 파티의 수
4 3
진실을 아는 사람의 수 / 그 번호
0
각 파티마다 오는 사람의 수 / 그 번호
2 1 2
1 3
3 2 3 4
- 예제 출력 1 -
3
- 예제 입력 2 -
4 1
진실을 아는 사람의 수 / 그 번호
1 1
각 파티마다 오는 사람의 수 / 그 번호
4 1 2 3 4
- 예제 출력 2 -
0
- 예제 입력 3 -
4 1
0
4 1 2 3 4
- 예제 출력 3 -
1
- 예제 입력 4 -
각 파티마다 오는 사람의 수 / 그 번호
4 5
진실을 아는 사람의 수 / 그 번호
1 1
각 파티마다 오는 사람의 수 / 그 번호
1 1
1 2
1 3
1 4
2 4 1
- 예제 출력 4 -
2
- 예제 입력 5 -
사람의 수 / 파티의 수
10 9
4 1 2 3 4
각 파티마다 오는 사람의 수 / 그 번호
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4
- 예제 출력 5 -
4
- 예제 입력 6 -
8 5
3 1 2 7
2 3 4
1 5
2 5 6
2 6 8
1 8
- 예제 출력 6 -
5
- 반례 1 -
4 5
1 1
1 1
1 2
1 3
2 4 2
2 4 1
- 출력 -
1
(3) 코드
import sys
def input():
return sys.stdin.readline().rstrip()
# fixme - 사람의 수 / 파티의 수
n, m = map(int, input().split())
# fixme - 진실을 아는 사람의 수 / 그 번호
temp1 = list(map(int, input().split()))
# 진실을 아는 사람이 있는 경우
if len(temp1[1:]) >= 1:
set_temp = set(temp1[1:])
# 진실을 아는 사람이 없는 경우
else:
set_temp = {}
cnt = 0
# fixme - parties 에는 각 파티와 구성원을 담아줄 것 입니다.
parties = []
for _ in range(m):
# fixme - temp2 에는 문제에서 주어지는 파티의 구성원을 담아줍니다.
temp2 = list(map(int, input().split()))
parties.append(temp2)
flag = False
for t in temp2[1:]:
# fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
if t in set_temp:
flag = True
# fixme - 해당 파티에 있는 모든 사람들을 set_temp 에 추가해준다. (진실을 아는 사람이 됩니다.)
if flag == True:
for t2 in temp2[1:]:
set_temp.add(t2)
for party in parties:
flag = False
for p in party[1:]:
# fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
if p in set_temp:
flag = True
# fixme - 파티원 중 아무도 진실을 알지 못하는 경우
if flag == False:
cnt += 1
print(cnt)
(4) 정리
이 문제에서 좀 더 설명이 추가한 부분은 시간 순서와 상관없이 이전 파티였어도 이후에 진실을 아는 구성원과 파티를 이룬적이 있는 구성원은 해당 구성원이 속했던 전에 파티에 있던 사람도 진실을 알게끔 처리해주어야 합니다. (마치 타임머신을 타고오듯?) 그래서 해당 구성원들을 모두 연결 시켜주어야 하며 이때 사용한 개념이 유니온 파인드입니다. 해당 알고리즘을 몰라 동빈나님 영상을 참고하고 구현하였습니다.
- 예제 입력 1 -
사다리의 수 / 뱀의 수
3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17
- 예제 출력 1 -
3
(1) 5를 굴려 6으로 이동한다.
(2) 6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
(3) 2를 굴려 100으로 이동한다.
- 예제 입력 2 -
사다리의 수 / 뱀의 수
4 9
8 52
6 80
26 42
2 72
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 21
- 예제 출력 2 -
5
(1) 5를 굴려 6으로 이동하고, 사다리를 이용해 80으로 이동한다.
(2) 6을 굴려 86으로
(3) 6을 또 굴려 92로
(4) 6을 또 굴려 98로 이동하고
(5) 2를 굴려 100으로 이동한다.
- 반례 1 -
2 1
7 94
8 94
55 54
- 출력 1 -
2
(3) 코드
import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
# 사다리의 수, 뱀의 수
n, m = map(int, input().split())
# graph
graph = [[0 for _ in range(10)] for _ in range(10)]
visited = [[0 for _ in range(10)] for _ in range(10)]
cnt = [[0 for _ in range(10)] for _ in range(10)]
k = int(1)
for i in range(10):
for j in range(10):
graph[i][j] = k
k = k + 1
# fixme - 사다리 (ladder) 딕셔너리와 뱀 (snake) 딕셔너리 정의
l = {}
s = {}
# fixme - 사다리 만들어주기
for _ in range(n):
start, end = map(int, input().split())
l[start] = end
# fixme - 뱀 만들어주기
for _ in range(m):
start, end = map(int, input().split())
s[start] = end
# fixme - 현재 위치마다 이동할 수 있는 범위를 체크해줍니다.
def can_move_range(x, y):
if x <= 8:
if y <= 3:
d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]
elif y == 4:
d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, -4]]
elif y == 5:
d = [[0, 1], [0, 2], [0, 3], [0, 4], [1, -5], [1, -4]]
elif y == 6:
d = [[0, 1], [0, 2], [0, 3], [1, -6], [1, -5], [1, -4]]
elif y == 7:
d = [[0, 1], [0, 2], [1, -7], [1, -6], [1, -5], [1, -4]]
elif y == 8:
d = [[0, 1], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]
elif y == 9:
d = [[1, -9], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]
elif x == 9:
if y <= 3:
d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]
elif y == 4:
d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
elif y == 5:
d = [[0, 1], [0, 2], [0, 3], [0, 4]]
elif y == 6:
d = [[0, 1], [0, 2], [0, 3]]
elif y == 7:
d = [[0, 1], [0, 2]]
elif y == 8:
d = [[0, 1]]
elif y == 9:
d = [[0, 0]]
return d
def roll_the_dice(sx, sy, cnt):
q = deque([])
q.append((sx, sy))
while q:
x, y = q.popleft()
d = can_move_range(x, y)
for i in range(len(d)):
nx = x + d[i][0]
ny = y + d[i][1]
# fixme - 아직 방문하지 않았고
if 0 <= nx <= 9 and 0 <= ny <= 9:
if visited[nx][ny] != 1:
# fixme - 사다리 인 경우
if graph[nx][ny] in l.keys():
target = l[graph[nx][ny]]
for x1 in range(10):
for y1 in range(10):
if graph[x1][y1] == target and visited[x1][y1] != 1:
q.append((x1, y1))
visited[nx][ny] = 1
visited[x1][y1] = 1
cnt[x1][y1] = cnt[x][y] + 1
# fixme - 뱀인 경우
if graph[nx][ny] in s.keys():
target = s[graph[nx][ny]]
for x1 in range(10):
for y1 in range(10):
if graph[x1][y1] == target and visited[x1][y1] != 1:
q.append((x1, y1))
visited[nx][ny] = 1
visited[x1][y1] = 1
cnt[x1][y1] = cnt[x][y] + 1
# fixme - 그냥 칸만 있는 경우
else:
q.append((nx, ny))
visited[nx][ny] = 1
cnt[nx][ny] = cnt[x][y] + 1
return cnt
cnt = roll_the_dice(0, 0, cnt)
print(cnt[9][9])
(4) 정리
'그림1'과 같은 경우 노란색 사다리를 타면 도착지점에 빨리 갈 수 있는 것처럼 보이지만 사실상 파란색 사다리를 타야 도착지점에 도달할 수 있습니다. 따라서 현재위치와 가까운 사타리를 타고 내려가는게 아닌 모든 칸에 대해서 몇번의 주사위를 굴려야 도착할 수 있는지 완전탐색해주어야 합니다.
풀이의 대부분이 1차원 배열로 구현해서 풀었습니다. 저는 처음에 2차원 배열로 구상하고 풀었기 때문에 j <= 3 열이 3이하인 경우 해당 행에서 6칸을 이어서 나아갈 수 있지만 i == 4 인 경우부터 i == 9 인 경우까지는 주사위를 굴릴시 열이 바뀌는 경우가 생깁니다. 해당 경우를 모두 고려하여 코드로 작성해주었습니다. 또한 i == 9 이면서 j >= 4 인 경우에는 더 이상 나아갈 수 있는 칸이 없어 해당 경우도 따로 elif 문으로 빼주었습니다. 해당 문제는 1차원 배열로 구현해서 푸는게 훨씬 쉽게 풀 수 있을거라 생각됩니다.
1. 아이디어
>> 상어의 위치를 찾고
>> 가장 가까운 거리의 물고리를 찾을때 visited 배열을 이용한다.
>> 가장 가까운 거리의 물고기를 찾는다. dfs() 이용
>> 이동 가능여부 판단 함수를 만든다 ---- 종료조건 ★
>> graph 에 있는 숫자가 0 또는 size 보다 큰 경우 더 이상 먹을 수 있는 먹이가 없다.
>> graph 에 있는 숫자가 0 또는 size 작은경우 먹을 수 있는 먹이가 있다.
2. 시간복잡도
>>
3. 자료구조
>>
import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
size = 2
feed = 0
dist = 0
check3 = 0
# fixme - 최초 상어의 위치를 찾는다.
for i in range(n):
for j in range(n):
if graph[i][j] == 9:
sx = i
sy = j
# fixme - 더이상 먹을 수 있는 먹이가 없는 경우 종료시킨다.
def ending():
flag = False
for i in range(n):
for j in range(n):
# 자기 자신은 먹이가 아니므로 건너뛴다.
if graph[i][j] == 9:
continue
# 먹이를 찾은 경우
elif graph[i][j] != 0 and graph[i][j] < size:
flag = True
return flag
# fixme - 먹이 먹을 곳을 찾자
def feeding(dist_check, feed, size):
if len(dist_check) == 0:
exit()
return False
dist_check = list(dist_check)
dist_check.sort(key = lambda x:[x[2], x[0], x[1]])
tx, ty, d = dist_check[0]
feed += 1
if feed == size:
feed = 0
size += 1
return tx, ty, d, feed, size
def iterative_dfs(sx, sy, graph, dist, visited):
global feed
global size
global check3
feed = 0
size = 2
while ending():
if check3 == 1:
break
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
q = deque([])
q.append((sx, sy))
graph[sx][sy] = 0
dist_check = deque([])
while q:
x, y = q.popleft()
min_dist = 10000000
# fixme - 사방이 막혀있거나 이동할 수 없는 경우
check1 = 0
check2 = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
check1 += 1
if graph[nx][ny] > size:
check2 += 1
if check1 == check2:
check3 = 1
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
# fixme - 먹이를 먹을 수 있는 경우 - 좌표와 거리만 체크해둔다.
if graph[nx][ny] != 0 and graph[nx][ny] < size:
if min_dist >= visited[x][y] + 1:
min_dist = visited[x][y] + 1
dist_check.append((nx, ny, visited[x][y] + 1))
# fixme - 이동만 가능한 경우
elif graph[nx][ny] == size or graph[nx][ny] == 0:
if visited[nx][ny] == 0:
q.append((nx, ny))
visited[nx][ny] += visited[x][y] + 1
# fixme - 먹이를 먹을 수 없는 경우
else:
visited[nx][ny] = -1
if len(dist_check) >= 1:
sx, sy, d, feed, size = feeding(dist_check, feed, size)
elif len(dist_check) == 0:
d = 0
# fixme - 먹이를 먹을 수 있는 경로를 아무것도 못찾은 경우
if d == 0 and dist == 0:
return 0
elif d == 0 and dist != 0:
return dist
dist += d
# fixme - 재정비한다.
graph[sx][sy] = 9
visited = [[0 for _ in range(n)] for _ in range(n)]
return dist
dist = iterative_dfs(sx, sy, graph, dist, visited)
print(dist)
(4) 정리
전에 풀어봤던 문제임에도 오래간만에 다시 푸는데 막히는 부분이 있었습니다. 참고 링크에 제가 막혔던 부분에 대해서 질문하고 답변받아 해결했습니다.