IT-garden

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력과 출력

알고리즘 분류

BFS

정답

import sys
from collections import deque

input= lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())

a = [list(map(int, input())) for i in range(n)]

ch=[[0]*m for i in range(n)]
dx = [-1, 0, 1, 0] #위,오른쪽,아래,왼쪽 
dy = [0, 1, 0, -1]

de=deque()
de.append([0,0])
ch[0][0]=1

while len(de) != 0:
    x, y = de.popleft()
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if a[nx][ny] != 0 and ch[nx][ny] == 0:    
                ch[nx][ny] = ch[x][y] + 1
                de.append([nx, ny])

print(ch[n-1][m-1])

백준 알고리즘 2178번 : www.acmicpc.net/problem/2178

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스

정답

from itertools import combinations

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

c = [[i,j] for i in range(n) for j in range(n) if a[i][j] == 2]
h = [[i,j] for i in range(n) for j in range(n) if a[i][j] == 1]

c_list = list(combinations(c, m))

def cal_d(h, c):
    min_dist = 1e9 #1e9 = 1*10^9
    
    for ch in c:
        dist = abs(ch[0] - h[0]) + abs(ch[1] - h[1])
        min_dist = min(min_dist, dist)
        
    return min_dist

b = []
for i in c_list:
    t = 0
    for j in h:
        t += cal_d(j,i)
    b.append(t)

print(min(b))

1. 도시 정보 리스트에서 치킨집 위치와 집 위치를 나타내는 좌표가 있는 리스트를 새로 만들어줍니다.

2. 치킨집 위치 리스트 중 m개를 뽑아서 조합합니다.

3. 치킨집의 조합별 집의 최단거리를 계산합니다.

4. 치킨집의 조합별 최단거리의 합이 가장 작은 것을 출력합니다.

백준 알고리즘 15686번 : www.acmicpc.net/problem/15686

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

from collections import deque

a=int(input())
b=int(input())

n=[list(map(int,input().split())) for i in range(b)]
m=[[] for i in range(a+1)]

ch=[0]*(a+1)

for i in range(b):
    x, y= n[i]
    m[x].append(y)
    m[y].append(x)

s=1 #시작점

def bfs(s):
    c=0 
    de=deque()
    de.append(s)
    ch[s]=1

    while len(de) != 0:
        d=de.popleft() 
        c += 1

        for i in m[d]:
            if ch[i] != 1:
                ch[i]=1
                de.append(i)
        
    print(c-1)
    
bfs(s)

백준 알고리즘 2606번 : www.acmicpc.net/problem/2606

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

n,m,v=map(int,input().split())

a=[[] for i in range(n+1)]

for i in range(m):
    x, y=map(int,input().split())
    a[x].append(y)
    a[y].append(x)

for i in a:
    i.sort()

def dfs(node):
    ch[node]=1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

ch=[0]*(n+1)
dfs(v)

print()

def bfs(start):
    de=deque()
    de.append(start)
    che[start]=1

    while len(de) != 0:
        now=de.popleft()
        print(now, end=' ')
        
        for i in a[now]:
            if che[i] != 1:
                che[i]=1
                de.append(i)
    
che=[0]*(n+1)
bfs(v)

queue를 사용하면 런타임 에러가 나서 deque를 사용했습니다.

queue가 많이 느려서 그렇다고 하는데 정확하지는 않습니다.

백준 알고리즘 1260번 : www.acmicpc.net/problem/1260

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import combinations_with_replacement

n,m=map(int,input().split())

a=list(map(int,input().split()))
a.sort()
a=list(combinations_with_replacement(a, m))

a=sorted(list(set(a)))

for i in a:
    print(*i)

백준 알고리즘 15666번 : www.acmicpc.net/problem/15666

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import product

n,m=map(int,input().split())

a=list(map(int,input().split()))
a.sort()
a=list(product(a, repeat=m))

a=sorted(list(set(a)))

for i in a:
    print(*i)

백준 알고리즘 15665번 : www.acmicpc.net/problem/15665