문제 설명:

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

문제 풀이:

위와 같이 경로를 탐색해야 하는 경우 깊이/너비 우선 탐색으로 풀어야 하는 경우가 많고, 이 문제 역시 깊이 우선 탐색(DFS)로 풀어야 하는 문제였다. 깊이 우선 탐색은 stack을 이용하고, 너비 우선 탐색은 queue를 사용하는데, python의 list는 stack가 비슷하게 작동을 하기 때문에 stack이라는 리스트를 만들었고, 이미 지나왔던 경로임을 표시하기 위해서 visited라는 bool list를 만들었다.
A 컴퓨터에서 시작해서 지나가는 컴퓨터들을 전부 True로 바꾸면서 이동을 하였고, 더 이상 움직일 수 없을 때까지 반복을 하도록 하였다. 그리고 또한 이 과정을 하나의 count로 취급해 하나의 network가 생겼다고 생각을 하였다. 따라서 모든 컴퓨터가 True가 될 때까지 이 count를 반복해서 하면 network의 수를 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def Network(computers,visited,SNode):
    stack=[SNode]
    while stack:
        path = stack.pop()
        if not visited[path]:
            visited[path]=True
        for i in range(len(computers)):
            if computers[path][i]==1 and not visited[i]:
                stack.append(i)
def solution(n,computers):
    answer=0
    visited=[False for i in range(n)]
    idx=0
    while not all(visited):
        if not visited[idx]:
            Network(computers,visited,idx)
            answer+=1
        idx+=1
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1011. Fly me to the Alpha Centauri  (0) 2019.07.05
[Programmers]Lv 3. 여행경로  (0) 2019.07.04
[BOJ]11057. 오르막 수  (0) 2019.07.01
[BOJ]1436. 영화감독 숌  (0) 2019.06.29
[BOJ]1018. 체스판 다시 칠하기  (0) 2019.06.28

문제:

두 개의 단어 begin,target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"] 라면 "hit" -> "hot" -> "dot" ->"dog" ->"cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin,target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS) 중 너비 우선 탐색을 사용하는 문제이다. begin에서 변환 할 수 있는 경우의 수를 만들어 주고 이 중에서 target이 있는지 확인한다. 없다면 이 경우의 수를 누적하여 다음 단계를 진행한다. 즉 1단계에서 만들어질수 있는 모든 경우, 2단계에서 만들어지는 경우..가 되는 것이다. 어짜피 target이 있는 층만 알면 되기에 문제 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(begin,target,words):
    answer=[begin]
    if target not in words:
        return 0
    answer_count=0
    while(len(words)!=0):
        for i in answer:
            temp=[]
            for word in words:
                count=0
                for j in range(len(i)):
                    if i[j]!=word[j]:
                        count+=1
                    if count==2:
                        break
                if count==1:
                    temp.append(word)
                    words.remove(word)
        answer_count+=1
        if target in temp:
            return answer_count
        else:
            answer=temp
    return 0
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22

문제:

 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1,1,1,1,1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1=3
+1-1+1+1+1=3
+1+1-1+1+1=3
+1+1+1-1+1=3
+1+1+1+1-1=3

 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟
넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.


1
2
3
4
5
6
7
8
9
10
def solution(numbers, target):
    answer_list=[0]
    for i in numbers:
        temporary_list=[]
        for j in answer_list:
            temporary_list.append(j+i)
            temporary_list.append(j-i)
        answer_list=temporary_list
    answer = answer_list.count(target)
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25

+ Recent posts

티스토리툴바