오늘의 알고리즘, 소프티어 회의실 예약, 순서대로 방문하기

오늘의 알고리즘 연습

 

회의실 예약

 

문제

문제에 대한 설명
https://softeer.ai/practice/6266

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이

N, M = map(int, input().split())
rooms = [input().rstrip() for _ in range(N)]
roomToCheckAvailable = {}

times = []
for start in range(9, 18+1):
  for end in range(18, start, -1):
    times.append((start, end))

for room in rooms:
  roomToCheckAvailable[room] = [True] * len(times)

for _ in range(M):
  room, s, e = input().rstrip().split()
  s, e = int(s), int(e)

  for idx, time in enumerate(times):
    if time[1] > s and time[0] < e:
      roomToCheckAvailable[room][idx] = False

for room_number, room in enumerate(sorted(rooms)):
  print(f"Room {room}:")
  numberOfAvailable = sum(roomToCheckAvailable[room])

  if not numberOfAvailable:
    print("Not available")
  else:
    numberOfAvailable = 0
    last_e = 0
    stack_avail = []
    for idx, check in enumerate(roomToCheckAvailable[room]):
      if check and times[idx][0] >= last_e:
        last_e = times[idx][1]
        numberOfAvailable += 1
        stack_avail.append((times[idx][0], times[idx][1]))
    print(str(numberOfAvailable) + " available:")
    for avail in stack_avail:
      print("{:02d}-{:02d}".format(avail[0], avail[1]))
  if room_number < len(rooms) - 1:
    print("-----")

코드가 엉망이라 말로 풀자면,
각 회의실마다 회의 가능한 시간을 모두 리스트로 지정한다.
예를 들면 [9-10, 9-11, ... , 9-18, 10-11, ...]
정확히는 회의실마다 위 리스트에 대응되는 True 리스트로 딕셔너리를 만든다.
그 다음에 예약된 회의실을 받을 때마다
위 리스트에 불가능한 시간대를 False로 전환한다.

이렇게 처리했을 때의 문제점 중 하나는
동일한 시작 시간대로 여러 가지 가능한 경우가 남는다는 것과
출력한 시간대보다 작은 시간대를 출력할 수 있다는 것이다.

첫 번째를 해결하기 위해서 last_e 변수를 선언하여 마지막에 출력한 시간대의 끝나는 시간보다 크거나 같은 시간대만 출력하도록 했고
두 번째를 해결하기 위해서 9-10, 9-11의 순이 아닌 9-18, 9-17처럼 끝나는 시간이 큰 순서대로 리스트를 만들었다.

추가로 자리수에 맞춰서 0을 붙이는 것은 format과 :02d로 구현할 수 있다.

 

순서대로 방문하기

 

문제

https://softeer.ai/practice/6246

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dest = []
for _ in range(m):
  x, y = map(int, input().split())
  dest.append((x-1, y-1))

# dfs
def dfs(cur_pos, dest_idx):
  global cnt

  if cur_pos == dest[dest_idx]:
    if dest_idx == m-1:
      cnt += 1
      return
    dest_idx += 1

  x, y = cur_pos
  visited[x][y] = True
  for i in range(4):
    nx, ny = x+dx[i], y+dy[i]
    if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and not grid[nx][ny]:
        dfs((nx, ny), dest_idx)
  visited[x][y] = False
              
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[False]*n for _ in range(n)]
cnt = 0

dfs(dest[0], 1)

print(cnt)

 

완전 탐색 문제에서 중간 목표지점을 둔 문제이다.

경로가 중요하기 때문에 dfs로 구현하고 dfs 함수가 종료되기 전에 현재 자리의 방문을 False로 되돌려 놓는다.

 

경험상 dfs 구현에 조심해야 하는 점은

첫 째로 재귀함수로 구현해서 반환하는 값을 사용하기 까다로울 수 있어 되도록 사용하지 않는다와

다음으로 재귀가 끝나고 올라오면서 필요한, 그러니깐 return 이후에 해야할 처리가 있느냐이다.(위 예에서는 visited[x][y] = False)