๋ฌธ์ œ๋ณด๋Ÿฌ๊ฐ€๊ธฐ

๐Ÿ•ต๏ธ‍โ™€๏ธ ๋ฌธ์ œ


๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ , ์ปดํ“จํ„ฐ B์™€ ์ปดํ“จํ„ฐ C๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์„ ๋•Œ ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ C๋„ ๊ฐ„์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ปดํ“จํ„ฐ A, B, C๋Š” ๋ชจ๋‘ ๊ฐ™์€ ๋„คํŠธ์›Œํฌ ์ƒ์— ์žˆ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ปดํ“จํ„ฐ์˜ ๊ฐœ์ˆ˜ n, ์—ฐ๊ฒฐ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด computers๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋„คํŠธ์›Œํฌ์˜ ๊ฐœ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

 

์ œํ•œ์‚ฌํ•ญ

  • ์ปดํ“จํ„ฐ์˜ ๊ฐœ์ˆ˜ n์€ 1 ์ด์ƒ 200 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์ปดํ“จํ„ฐ๋Š” 0๋ถ€ํ„ฐ n-1์ธ ์ •์ˆ˜๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  • i๋ฒˆ ์ปดํ“จํ„ฐ์™€ j๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด computers[i][j]๋ฅผ 1๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  • computer[i][i]๋Š” ํ•ญ์ƒ 1์ž…๋‹ˆ๋‹ค.

 

 

๐Ÿ™‹‍โ™€๏ธ ํ’€์–ด๋ณด์ž~


DFS์™€ BFS๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋‹ค.

๋‘ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์„ ๋ชจ๋‘ ํ•ด๋ณด์ž!

 

1. DFS๋กœ ํ’€์–ด๋ณด๋ฉด,,,

  • ๋ฐฉ๋ฌธ์„ ํ–ˆ๋Š”์ง€ ํ™•์ธ์„ ๋„์™€์ค„ visited ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•œ๋‹ค.

 

def dfs(n, computers, com, visited):
  # dfs ๋Œ๊ธฐ ์œ„ํ•œ ์ปดํ“จํ„ฐ๋Š” ์šฐ์„  ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ์ฐ๋Š”๋‹ค.
  visited[com] = True
  
  # ์ปดํ“จํ„ฐ๋“ค ๊ฐœ์ˆ˜๋งŒํผ for๋ฌธ ๋Œ๋ ค์„œ com๊ณผ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ  ๋ฐฉ๋ฌธํ•œ์  ์—†๋Š” ๊ฒƒ์„ ์ฐพ๋Š”๋‹ค.
  # ์ฐพ์œผ๋ฉด ์–˜๋„ dfs๋Œ๋ฆฐ๋‹ค.
  for connect in range(n):
    if connect != com and computers[com][connect] == 1:
      if visited[connect] == False:
        dfs(n, computers, connect, visited)


def solution(n, computers):
  answer = 0
  # ๋ฐฉ๋ฌธํ•œ ๊ธฐ๋ก์„ ๋‚จ๊ธฐ๋Š” visited
  # ๋ฐฉ๋ฌธํ•œ ์ ์ด ์—†์œผ๋ฉด False๋‹ค.
  visited = [False] * n
  
  # ์ปดํ“จํ„ฐ ํ•œ๋Œ€์”ฉ ๋Œ๋ ค๋ณด๋ฉฐ ๋ฐฉ๋ฌธํ•œ ์  ์—†๋Š” ์ปดํ“จํ„ฐ๋ฅผ ์ฐพ์•„
  # dfsํ•ด์ฃผ๊ณ , ํ•œ๋ฒˆ ๋๋‚˜๋ฉด answer์— 1์„ ๋”ํ•ด์ค€๋‹ค.
  for com in range(n):
    if visited[com] == False:
      dfs(n, computers, com, visited)
      answer += 1
      
  return answer;

 

 

2. BFS๋กœ ํ’€์–ด๋ณด๋ฉด,,,

dfs์™€ ๋‹ฌ๋ฆฌ deque ๋ฑ์„ import ํ•ด์ค˜์•ผ ํ•œ๋‹ค.

 

from collections import deque

def bfs(n, computers, com, visited):
  # ๋ฑ์— ํ˜„์žฌ com ๋ฒˆํ˜ธ๋ฅผ ๋„ฃ์–ด์ค€๋‹ค.
  q = deque([com])
  
  # ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ํ‘œ์‹œํ•ด
  visited[com] = True
  
  # q๋ฅผ ๋Œ๋ฆฌ๋ฉด์„œ popleft ํ•ด์ฃผ๊ณ ... ๋“ค๋ ค์ค˜์•ผํ•˜๋Š” ์• ๋ฉด appendํ•ด์ค€๋‹ค
  while q:
    com = q.popleft()
    for connect in range(n):
      if connect!=com and computers[com][connect]==1 and not visited[connect]:
        q.append(connect)
        visited[connect] = True

def solution(n, computers):
  answer = 0
  visited = [False] * n
  for com in range(n):
    if visited[com] == False:
      bfs(n, computers, com, visited)
      answer += 1

  return answer;

๋ฌธ์ œ๋ณด๋Ÿฌ๊ฐ€๊ธฐ

๐Ÿ•ต๏ธ‍โ™€๏ธ ๋ฌธ์ œ


 

 

 

๐Ÿ™‹‍โ™€๏ธ ํ’€์–ด๋ณด์ž~


1. ๋‹ค๋ฆฌ ์œ„์— ์žˆ๋Š” ํŠธ๋Ÿญ๋“ค์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋”ฐ๋กœ ๋งŒ๋“ค์ž.

trucks_on_bridge -> ์—ฌ๊ธฐ์„œ len๋Š” bridge_length๋กœ ์ค€๋‹ค. ๊ทธ ๊ธธ์ด๋งŒํผ๋งŒ ํŠธ๋Ÿญ์ˆ˜๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ

 

2. ์ด์ œ ๋‹ค๋ฆฌ์— ์˜ฌ๋ผ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ฐจ ๋Œ€์ˆ˜๋งŒํผ while๋ฌธ์„ ๋นŒ๋ฆฌ๋ฉด์„œ ์ง„ํ–‰ํ•œ๋‹ค.

๋‹ค๋ฆฌ์— ์˜ฌ๋ผ์™€ ์žˆ๋Š” ํŠธ๋Ÿญ์ด ์žˆ์œผ๋ฉด ๋งจ ์•ž์— ์žˆ๋Š” ํŠธ๋Ÿญ์„ ๋นผ์ฃผ๊ณ 

ํ˜„์žฌ ๋‹ค๋ฆฌ์— ์žˆ๋Š” ํŠธ๋Ÿญ๋“ค์˜ ํ•ฉ๊ณผ ์ƒˆ๋กœ ํˆฌ์ž…๋˜๊ธฐ๋ฅผ ๊ธฐ๋‹ค๋ฆฌ๋Š” truck_weights[0]์„ ํ•ฉํ–ˆ์„ ๋•Œ ๊ฒฌ๋”œ ์ˆ˜ ์žˆ๋Š”์ง€ ์ฒดํฌํ•œ๋‹ค.

๋œ๋‹ค๋ฉด ๋‹ค๋ฆฌ์— ์˜ฌ๋ ค์ฃผ๊ณ  ๋Œ€๊ธฐ ๋ชฉ๋ก์—์„œ ๋นผ์ค€๋‹ค.

์•ˆ๋œ๋‹ค๋ฉด ๊ทธ๋ƒฅ 0์„ ๋„ฃ์–ด์„œ ์˜ฌ๋ฆฌ์ง€ ๋ชปํ–ˆ์Œ์„ ๋ช…์‹œํ•œ๋‹ค.

 

 

 

 

def solution(bridge_length, weight, truck_weights):
    answer = 0
    trucks_on_bridge = [0] * bridge_length
    while len(trucks_on_bridge):
        answer += 1
        trucks_on_bridge.pop(0)
        if truck_weights:
            if sum(trucks_on_bridge) + truck_weights[0] <= weight:
                trucks_on_bridge.append(truck_weights.pop(0))
            else:
                trucks_on_bridge.append(0)
    return answer

 

 

<์ฐธ๊ณ ํ• ๋งŒํ•œ ๋‹ต์•ˆ>

import collections

DUMMY_TRUCK = 0


class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count


def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()

+ Recent posts