Henry's Algorithm

문제 설명

두 개의 단어 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 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin     target     words     return

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

문제 푸는 방법:

최단경로를 찾는 문제이다.

힌트는 한번에 1개의 단어만 변할 수 있다고 하는 부분에서 edge라고 생각하여 graph를 그릴 수 있다.

그래프를 그린 후에 target 노드까지 가는 최단 경로를 BFS 알고리즘을 통해 구해주면 된다.

정답 코드:

from collections import defaultdict

def solution(begin, target, words):
    if target not in words:
        return 0
    answer = 0
    graph = defaultdict(set)
    words.append(begin)
    for i in range(len(words)-1):
        for j in range(i+1,len(words)):
            if is_convert(words[i],words[j]):
                graph[words[i]].add(words[j])
                graph[words[j]].add(words[i])
    
    result = BFS(graph,begin)
    return result[target]

def BFS(graph, start):
    visited = {}
    queue = [(start,0)]
    
    while queue:
        cur = queue.pop(0)
        if cur[0] not in visited:
            visited[cur[0]] = cur[1]
            arr = set(graph[cur[0]]) - set(visited)
            queue.extend([(i,cur[1]+1) for i in arr])
    return visited

def is_convert(begin,target):
    cnt = 0
    for x,y in zip(begin,target):
        if x!=y:
            cnt += 1
    if cnt == 1:
        return True
    else:
        return False

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

문제 푸는 방법:

BFS 알고리즘으로 한 칸씩 가면서 Count를 +1 씩 해주면된다.

마지막 Visited 리스트에서 Counter 함수를 통해 중복값끼리 모으고 Sorting 하여 최대값을 알아낸다.

정답 코드:

from collections import deque, Counter

def solution(n, edge):
    answer = 0
    graph = {}
    for i in edge:
        if i[0] in graph:
            graph[i[0]].append(i[1])
        else:
            graph[i[0]] = [i[1]]
        if i[1] in graph:
            graph[i[1]].append(i[0])
        else:
            graph[i[1]] = [i[0]]
    
    result = bfs(graph,1)
    result = sorted(result.values(), reverse=True)
    return list(Counter(result).values())[0]

def bfs(edge,root):
    visited = {}
    queue=deque([[root,0]])
    arr = [[root,0]]
    while queue:
        current = queue.popleft()
        if current[0] not in visited:
            visited[current[0]] = current[1]
            add = set(edge[current[0]]) - set(visited)
            queue += ([[i,current[1]+1] for i in add])
    return visited

나의 생각:

드디어 경로 문제의 첫 발을 띄었다.

항상 알고리즘 문제에서 경로 문제를 제일 어려워했는데,

프로그래머스의 Level 2의 조금 쉬운 문제로 시작했다.

생각보다 어려운 공식이 아니었다. 앞으로 경로 문제 풀 때 괜히 겁먹지 말자!

화이팅!!

NHN 코딩테스트를 대비하며 Java 로도 풀어보았다.

푸는 방식은 위의 파이썬 코드 설명과 같다. 화이팅!

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<edge.length; i++){
            list.add(new ArrayList<Integer>());
        }
        for(int[] i:edge){
            int a = i[0];
            int b = i[1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        int[] cnt = new int[n+1];
        cnt[0]=cnt[1] = 0;
        boolean[] visited = new boolean[n+1];
        visited[0]=visited[1] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);// 시작점
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int v:list.get(cur)){
                if(!visited[v]){
                    visited[v] = true;
                    cnt[v] = cnt[cur]+1;
                    q.add(v);
                }
            }
        }
        int max = 0;
        int ans = 0;
        for(int i: cnt){
            if(max<i){
                max = i;
                ans = 1;
            }else if(max == i){
                ans += 1;
            } 
        }
        
        return ans;
    }
}

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예

ncomputersreturn

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

프로그래머스의 LEVEL 3단계 문제이다.

풀이의 핵심은 DFS, BFS 함수를 정의하여 풀면 된다.

나는 DFS로 시작 컴퓨터 정하고, 깊이를 파고들어서 visit 리스트에 넣어주었다.

이후 다른 컴퓨터에 한번씩 접근했을 때

이전 컴퓨터를 통해 이미 visit 값에 포함되어 있다면 네트워크에 연결이 되어있는 컴퓨터라고 생각했다.

그래서 다른 컴퓨터에 접근할 때마다 visit가 늘어나게 되면 그 컴퓨터는 독립적인 네트워크라고 판단하여 문제를 풀었다.

풀이 코드

def solution(n, computers):
    
    # 네트워크 개수
    net_num = 0
    
    # 방문 컴퓨터 리스트
    visit = list()
    
    # 컴퓨터에 한번씩 접근하면서 깊이우선탐색 수행
    for i in range(len(computers)):
        net_num += dfs(computers,i,visit)
    
    return net_num


def dfs(computers, start_computer, visit):
    
    # 깊이 우선 탐색은 스택으로 구현한다.
    stack = list()
    
    # 신규 네트워크 여부
    is_connect = 0
    
    # 시작 컴퓨터
    stack.append(start_computer)
    
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend([i for i in range(len(computers[node])) if i != node and computers[node][i] != 0])
            is_connect = 1
            
    return is_connect

완전탐색이란 

모든 경우의 수를 다 찾아보는 해결 방법이다.

가령 자물쇠의 비밀번호를 찾는 문제가 나온다고 할 때,

가장 쉬운 방법은 0000 부터 9999까지 한번씩 다 해보면 그 중간에 정답을 찾을 수 있는 방법입니다.

구현하기 쉽지만 코딩테스트에서는 오랜 시간이 걸리게 되어 Timeout을 일으킬 수도 있는 방법론입니다.ㅜㅜ

그래도 중간중간 로직을 손봐주면 확실히 무작정 코드를 짜는 것보다는 정확도와 성능을 높일 수 있으니,

한번 공부해보시면 좋을 것 같습니다.

완전탐색의 종류

1. Brute Force : for 문과 if 문을 사용하여 전체를 다 살펴보기

관련 예제: 프로그래머스 K번째 수 문제 https://datacodingschool.tistory.com/86

2. 비트마스크 : 용어 그대로 비트에 관한 것이다. 

비트(bit)는 0과1로 이루어진 컴퓨터에서 사용되는 최소 단위이다. (0,1 혹은 true,false 혹은 on,off)

관련 예제: 백준 2098번, 외판원 순회 문제 https://www.acmicpc.net/problem/2098

이진수 -> 십진수

십진수 - > 이진수 로 변환시키면서 문제를 풀 수 있다.

또한 이진수로 비트 변환 시킨 상태에서 다양한 비트 연산을 할 수 있다.

& (AND) : 대응하는 두 비트가 모두 1일 때 1반환

1010 & 1111 = 1010

| (OR) : 대응하는 두 비트 중 하나라도 1일 때 1반환

1010 | 1101 = 1111

^ (XOR) : 대응하는 두 비트가 서로 다를 때 1 반환

1010 ^ 1111 = 0101

~ (NOT) : 비트를 모두 반대 방향으로 뒤집는 변환

~1010 = 0101

>>, << (쉬프트 연산) : 왼쪽이나 오른쪽으로 비트를 옮긴다.

0001101 << 3 = 1101000
0001101 >> 2 = 0000011

참고한 블로그를 살펴보면,

왼쪽 시프트는 A * 2^B 를 의미하고, 오른쪽 시프트는 A / 2^B 를 의미한다.

0001 -> 0010 -> 0100 -> 1000 => 1, 2, 4, 8 .....

1000 -> 0100 -> 0010 -> 0001 => 8, 4, 2, 1 ..... 

(A + B) / 2 를 (A + B) >> 1 로 사용할 수도 있듯이 많은 곳에서 일반적인 사칙연산을 더 효율적으로 할 수 있다.

출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]

3. 순열

순열(Permutation)은, 중복없이 원소들을 하나씩 뽑은 모든 경우의 수를 말한다.

예를 들어 {a,b,c,d}일 때, 2개를 뽑아서 일렬로 세우는 방법은 12가지

ab ac ad  ba bc bd  ca cb cd  da db dc 

경우의 수는 4*3 = 12이다.

4. 백트래킹

모든 경우의 수를 갈때, 비효율적인 루트는 차단하고, 가능성있는 곳을 탐색하는 알고리즘

관련 예제: 백준 9663 N-queen 문제, https://www.acmicpc.net/problem/9663

5. BFS, DFS

넓이우선탐색(BFS) : 현재 정점에 연결된 가까운 점들부터 탐색

깊이우선탐색(DFS) : 현재 정점에서 최대한 갈 수 있는 점까지 들어가면서 탐색

관련 예제: 백준 2667 단지번호붙이기 문제, https://www.acmicpc.net/problem/2667