문제:

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력:

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

풀이방법:

 맥주 한 박스에는 맥주가 20개 들어있고, 편의점에서 이를 채울 수 있다. 편의점에 도달하면 무조건 맥주를 가득 채우는 것이 이득이므로, 최대로 이동할 수 있는 거리는 1000미터다. 따라서 현재 있는 위치로부터 1000미터 이내에 편의점이 있거나 페스티벌을 하는 장소가 있는지 찾으면 된다. 

 따라서 페스티벌을 하는 장소에 도달하는지의 여부를 찾으면 되기 때문에 1000미터 이내에 도달할 수 있는 장소를 모두 저장하며 탐색하는 BFS 방법을 사용하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
from collections import deque
 
input = sys.stdin.readline
 
def bfs(start):
    x, y = start
    q = deque([(x,y)])
    while q:
        x, y = q.popleft()
        if (x,y) == (fx, fy):
            print("happy")
            return
        for i, v in enumerate(conven):
            if not visited[i]:
                nx, ny = v
                dist = abs(nx-x) + abs(ny-y)
                if 1000 >= dist:
                    q.append((nx,ny))
                    visited[i] = 1
    print("sad")
    return         
 
= int(input())
for _ in range(t):
    conven = []
    n = int(input())
    house = map(int,input().split())
    for _ in range(n):
        x, y = map(int, input().split())
        conven.append((x,y))
    fx, fy = map(int,input().split())
    conven.append((fx,fy))
    visited = [0]*len(conven)
    bfs(house)
cs

문제링크:

https://www.acmicpc.net/problem/9205

 

9205번: 맥주 마시면서 걸어가기

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.

www.acmicpc.net

 

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

[BOJ]2615. 오목  (0) 2022.04.12
[BOJ]2628. 종이자르기  (0) 2022.04.07
[BOJ]1439. 뒤집기  (0) 2022.03.31
[BOJ]2023. 신기한 소수  (0) 2022.03.29
[BOJ]1052. 물병  (0) 2022.03.24

문제:

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 A, B, C가 주어진다.

출력:

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

풀이방법:

A, B를 담을 수 있는 물통들을 기준으로 하여 visited 배열을 만들고, BFS를 수행하도록 한다. visited의 가능한 갯수는 A와 B에 담을 수 있는 경우의 수와 같다. 처음은 비어있기 때문에, (0,0)으로부터 시작하도록 한다. 매 C는 가지고 있는 A, B 물의 양을 통해 구하도록 한다. 가지고 있는 A, B, C 물의 양을 통해 이동할 수 있는 모든 경우에 대해 조사하도록 한다. (A-> B, A-> C, B->C, B-> A, C-> A, C-> B)와 같은 총 6가지 case가 존재한다. 가능한 모든 경우에 대해 BFS를 수행하며 A의 물의 양이 0인 경우에 C의 값을 저장하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from collections import deque
 
A, B, C = map(int,input().split())
 
queue = deque()
queue.append((0,0))
visited = [[0 for _ in range(B+1)] for _ in range(A+1)]
visited[0][0= 1
 
answer = []
while queue:
    x,y = queue.popleft()
    z = C-x-y
    if x==0:
        answer.append(z)
    
    #A->B
    water = min(x,B-y)
    if not visited[x-water][y+water]:
        visited[x-water][y+water] = 1
        queue.append((x-water,y+water))
    
    #A->C
    water = min(x,C-z)
    if not visited[x-water][y]:
        visited[x-water][y] = 1
        queue.append((x-water,y))
        
    #B->C
    water = min(y,C-z)
    if not visited[x][y-water]:
        visited[x][y-water] = 1
        queue.append((x,y-water))
        
    #B->A
    water = min(y,A-x)
    if not visited[x+water][y-water]:
        visited[x+water][y-water] = 1
        queue.append((x+water,y-water))
        
    #C->A
    water = min(z,A-x)
    if not visited[x+water][y]:
        visited[x+water][y] = 1
        queue.append((x+water,y))
 
    #C->B
    water = min(z,B-y)
    if not visited[x][y+water]:
        visited[x][y+water] = 1
        queue.append((x,y+water))
    
print(*sorted(answer))
cs

문제링크:

https://www.acmicpc.net/problem/2251

 

2251번: 물통

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부

www.acmicpc.net

 

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

[BOJ]11058. 크리보드  (0) 2021.11.01
[BOJ]14391. 종이 조각  (0) 2021.10.29
[BOJ] 15988. 1, 2, 3 더하기  (0) 2021.10.25
[BOJ] 13023. ABCDE  (0) 2021.10.22
[BOJ]1339. 단어 수학  (0) 2021.10.21

문제:

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력:

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

풀이방법:

 bfs를 사용하여 각 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역들의 넓이를 구한다. 전체 영역을 1로 초기화하고 직사각형의 꼭짓점을 입력값으로 받을 때, 내부 영역들을 0으로 재정의한다.

 이 과정을 모두 마친 뒤, (0,0)부터 bfs를 사용하여 분리된 영역들의 각 넓이를 구한다. 한 점으로부터 시작해 이동하면서 visited를 업데이트하여 중복적으로 이동하는 것을 막으며 더 이상 이동하지 못할 때, 하나의 분리된 영역의 넓이를 구한 것으로 파악한다.

 탐색하는 과정을 region이 1이고, 방문하지 않은(visited가 0인) 곳에 대해 반복적으로 BFS를 수행하고, 이 결과들을 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
dx = [-1,0,0,1]
dy = [0,1,-1,0]
 
def bfs(x,y):
    visited[y][x] = 1
    area = 1
    points = [(x,y)]
    while len(points):
        temp = []
        for point in points:
            x,y = point
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if 0<= nx < n and 0<= ny < m:
                    if region[ny][nx]==1 and not visited[ny][nx]:
                        area+=1
                        visited[ny][nx]=1
                        temp.append((nx,ny))
        points = temp
    return area
                
 
m,n,k = map(int,input().split())
region = [[1 for _ in range(n)]for _ in range(m)]
visited = [[0 for _ in range(n)]for _ in range(m)]
 
for _ in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    for x in range(x1,x2):
        for y in range(y1,y2):
            region[y][x] = 0
 
 
answers = []
for x in range(n):
    for y in range(m):
        if region[y][x] and not visited[y][x]:
            answer = bfs(x,y)
            answers.append(answer)
            
print(len(answers))
print(*sorted(answers))
cs

문제링크:

https://www.acmicpc.net/problem/2583

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

[BOJ]1422. 숫자의 신  (0) 2021.05.25
[BOJ]15686. 치킨 배달  (0) 2021.05.20
[BOJ]3055. 탈출  (0) 2021.05.11
[BOJ]2630. 색종이 만들기  (0) 2021.04.29
[BOJ]3273. 두 수의 합  (0) 2021.04.27

문제:

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력:

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력:

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

풀이방법:

 이 문제의 핵심은 물과 고슴도치의 이동을 BFS로 확인하면서 고슴도치가 비버의 집까지 갈 때까지 물의 영향을 받지 않는 지 확인해야 한다.

 우선 물에 대해서 BFS를 수행하면서 한 번 퍼질 때마다 1씩 늘어나면서 visit 배열이 채워진다. 이 때, 벽이나 비버의 집에는 물이 차지 않도록 한다.

 그 다음에는 고슴도치의 이동에 대해서 BFS를 수행하며 배열 안에 존재하며 비버의 집을 찾을 때 종료되도록 한다. 고슴도치가 이동할 때에는 물이 퍼진 정도에 따라 이동을 할 수 있으며, 물의 visit 배열 값보다 작을 때에만 이동할 수 있다. (물의 값이 4, 고슴도치가 이동할 값이 5라면 이동 불가 -> 물이 이미 차 있기 때문)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def main():
    from collections import deque
 
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
 
    r,c = map(int,input().split())
    hVisit = [[0 for _ in range(c)]for _ in range(r)]
    wVisit = [[0 for _ in range(c)]for _ in range(r)]
    forest = []
    Hedgehog = deque()
    water = deque()
    for i in range(r):
        temp = input()
        forest.append([])
        for j,t in enumerate(temp):
            if t == "X":
                forest[i].append(-1)
            elif t == "S":
                forest[i].append(1)
                Hedgehog.append((i,j))
                hVisit[i][j] = 1
            elif t == "*":
                forest[i].append(2)
                water.append((i,j))
                wVisit[i][j] = 1
            elif t == '.':
                forest[i].append(0)
            elif t == 'D':
                forest[i].append(3)
 
    while len(water):
        x,y = water.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if 0<=nx<and 0<=ny<and (forest[nx][ny]!=-1 and forest[nx][ny]!=3and not wVisit[nx][ny]:
                water.append((nx,ny))
                wVisit[nx][ny] = wVisit[x][y] + 1
    while len(Hedgehog):
        x,y = Hedgehog.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<and 0<=ny<and forest[nx][ny]==3:
                print(hVisit[x][y])
                return 0
            if 0<=nx<and 0<=ny<c:
                if forest[nx][ny] != -1 and not hVisit[nx][ny]:
                    if hVisit[x][y] + 1 < wVisit[nx][ny] or wVisit[nx][ny] == 0:
                        Hedgehog.append((nx,ny))
                        hVisit[nx][ny] = hVisit[x][y] +1
 
    print("KAKTUS")
    
if __name__ == "__main__":
    main()
cs

문제링크:

www.acmicpc.net/problem/3055

 

3055번: 탈출

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제

www.acmicpc.net

 

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

[BOJ]15686. 치킨 배달  (0) 2021.05.20
[BOJ]2583. 영역 구하기  (0) 2021.05.18
[BOJ]2630. 색종이 만들기  (0) 2021.04.29
[BOJ]3273. 두 수의 합  (0) 2021.04.27
[BOJ]9184. 신나는 함수 실행  (0) 2021.04.22

문제:

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력:

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력:

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이방법:

너비 우선 탐색의 가장 기초적인 문제다. 이미 지나온 곳을 다시 방문하지 않도록 0으로 초기화된 visited 배열을 만들었고, 현재 stage에서 나이트가 있을 수 있는 위치를 able이라는 배열에 저장하도록 했다. 

bfs 함수 내에선 우선 able 내에 목적지가 있는지 확인하는 과정을 먼저 거친다. 있다면 현재 stage(count)를 출력하도록 하고, 없으면 나이트가 움직일 수 있는 경우의 수인 candidate를 able을 각 케이스에 대해 더해줘서 새로운 able을 만들도록 한다. 이 과정을 재귀적으로 반복하면서 값을 찾는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
candidate = [(2,1),(1,2),(2,-1),(1,-2),(-1,2),(-1,-2),(-2,1),(-2,-1)]
def bfs(able,visited):
    global count
    if (eX,eY) in able:
        print(count)
    else:
        count+=1
        temp = []
        for a in able:
            for c in candidate:
                nx,ny = a[0]+c[0],a[1]+c[1]
                if 0<=nx<and 0<=ny<and visited[nx][ny]==0:
                    visited[nx][ny]=1
                    temp.append((nx,ny))
        bfs(temp,visited)
            
N=int(input())
for _ in range(N):
    l = int(input())
    sX,sY = map(int,input().split())
    eX,eY = map(int,input().split())
    visited = [[0 for _ in range(l)]for _ in range(l)]
    count=0
    able = [(sX,sY)]
    visited[sX][sY] = 1
    bfs(able,visited)
cs

문제링크:

www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

 

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

[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
[BOJ]1707. 이분 그래프  (0) 2020.11.24
[BOJ]1992. 쿼드트리  (0) 2020.11.17
[BOJ]1041. 주사위  (0) 2020.11.12
[BOJ]1059. 수2  (0) 2020.11.10

문제:

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

 

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

 

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다.(만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

 

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력:

첫째 줄에 F, S, G, U, D가 주어진다. (1<=S,G<=F<=1000000, 0<=U,D<=1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력:

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베티어로 이동할 수 없을 때는 "use the stairs"를 출력한다.

풀이방법:

 BFS로 경우의 수를 카운팅하면서 최소의 값을 찾을 수 있다. 우선 S와 G가 같으면 버튼을 누를 필요가 없기 때문에 0으로 답을 출력하도록 했다. 이제 이외의 경우에 대해서 BFS를 사용하기 위해, 초기 시작 층인 S로 state를 초기화 했고, 중복방문을 제거하기 위해서 visited를 초기화 했다.

 이제 갈 수 없는 경우( 0층, F층 초과)만 있을 때까지 계속 반복하기 위해서 while을 len(state) 초기화 했고, 현재 층을 s라고 할 때 다음과 같은 경우에만 이동하도록 한다.

 

1. s+U가 F층 이하이고, 방문하지 않은 곳이라면

2. s-F가 1층 이상이고, 방문하지 않은 곳이라면

 

이를 반복하면서 G가 나타나거나, 1,2 케이스가 하나도 없을 떄까지 반복해서 답을 구하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
F,S,G,U,D=map(int,input().split())
 
if S==G:
    state=[]
    correct=True
else:
    state=[S]
    visited=[0]*(F+1)
    visited[S]=1
    correct=False
answer=0
while len(state):
    temp=[]
    for s in state:
        if s+<= F and visited[s+U]==0:
            temp.append(s+U)
            visited[s+U]=1
        if s-> 0 and visited[s-D]==0:
            temp.append(s-D)
            visited[s-D]=1
    answer+=1
    if G in temp:
        correct=True
        state=[]
    else:
        state=temp
 
if correct:
    print(answer)
else:
    print("use the stairs")
            
cs

문제링크:

https://www.acmicpc.net/problem/5014

 

5014번: 스타트링크

문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없

www.acmicpc.net

 

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

[BOJ]2167. 2차원 배열의 합  (0) 2020.05.14
[BOJ]1350. 진짜 공간  (0) 2020.05.12
[2019 Kakao winter internship]튜플  (0) 2020.04.23
[2019 Kakao winter internship]크레인 인형뽑기 게임  (0) 2020.04.21
[BOJ]2863. 이게 분수?  (0) 2020.04.16

문제:

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

 

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력:

사람들은 1, 2, 3, ..., n (1<=n<=100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘때 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

 

각 사람의 부모는 최대 한 명만 주어진다.

출력:

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이 때에는 -1을 출력해야 한다.

풀이방법:

두 사람이 얼마나 긴 간격으로 연결되어 있는지 확인하는 문제이기 때문에 dfs나 bfs로 풀어야 할 것 같다고 생각했다. dfs로도 풀 수 있는지 정확히 모르지만, 두 사람 사이의 몇 level(단계)가 있는지 확인하면 되는 문제 이므로 bfs를 사용하기로 했다.

형제들 같은 경우에는 2촌으로 계산되는데 그 이유가 (나에서 부모님으로 1촌) + (부모님에서 형제로 1촌) 이기 때문이다. 따라서 이러한 관계를 알기 위해서는 양방향으로 이동할 수 있도록 relation을 만들었고, 중복방문을 하지 않기 위해서 visited를 만들었다.

처음 시작해야 하는 사람의 번호로 시작한다. 그리고 그 사람과 관계가 있는 사람들 중 방문하지 않았던 사람만 temp라는 배열에 담고 방문한 것으로 visited를 변경한다. 그리고 이 temp에 나와의 관계가 알고 싶은 사람의 번호가 있는지 확인하고, 있다면 break 없다면 temp의 길이를 재서 탐색할 사람이 있는지 확인한다. temp에 더 탐색할 사람이 있다면 위의 행동을 다시 반복하고, 더 이상 탐색할 사람이 없다면 친척 관계가 전혀 없다는 것으로 출력하면 된다.

그리고 최종 출력에서 +1을 했는데, 이 이유는 temp에 내가 원하는 사람의 번호가 있기 때문에 그 관계로 이동한다는 행동이 빠져있었기 때문에 +1을 해서 출력하도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
N=int(input())
a,b=map(int,input().split())
m=int(input())
 
relation = [[]for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
 
for _ in range(m):
    c,d = map(int,input().split())
    relation[c].append(d)
    relation[d].append(c)
    
answer = 0
re=relation[a]
while True:
    temp=[]
    for i in re:
        for j in relation[i]:
            if visited[j]==0:
                visited[j]=1
                temp.append(j)
    answer+=1
    if b in temp:
        find=True
        break
    if len(temp)==0:
        find=False
        break
    re = temp
if find:
    print(answer+1)
else:
    print(-1)
cs

문제링크:

https://www.acmicpc.net/problem/2644

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대

www.acmicpc.net

 

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

[BOJ]1302 베스트셀러  (0) 2020.04.07
[BOJ]1051. 숫자 정사각형  (0) 2020.03.26
[BOJ]2352. 반도체 설계  (0) 2020.03.19
[BOJ]1748. 수 이어 쓰기 1  (0) 2020.03.17
[BOJ]1267. 핸드폰 요금  (0) 2020.03.12

문제:

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

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

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

입력:

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

출력:

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

풀이 방법:

 1에 연결되어 있는 네트워크를 다 찾아야 하므로 깊게 계속 파고 들어가는 것 보다 너비를 우선 해서 탐색하는 편이 더 좋다. 우선 양방향으로 퍼질 수 있으므로 인덱스를 컴퓨터의 번호로 해서 리스트로 이동할 수 있는 컴퓨터를 담아두었다. 그 다음에는 answer리스트를 만들어두고 answer에는 없지만 갈 수 있는 곳이면 answer에 담고 이동을 하는 방식으로 답을 구하였다. 1번 컴퓨터를 제외한 컴퓨터의 수가 정답이므로 마지막에 1을 뺐다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n=int(input())
virus=int(input())
computer=[[] for i in range(n+1)]
for i in range(virus):
    a,b=map(int,input().split())
    if not a in computer[b]:
        computer[b].append(a)
    if not b in computer[a]:
        computer[a].append(b)
answer=[1]
def bfs(now):
    global answer
    for i in computer[now]:
        if not i in answer:
            answer.append(i)
            bfs(i)
bfs(1)
print(len(answer)-1)
cs


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

[BOJ]2075. N번째 큰 수  (0) 2019.07.23
[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙  (0) 2019.07.21
[BOJ]1260. DFS와 BFS  (0) 2019.07.19
[BOJ]2164. 카드2  (0) 2019.07.18
[BOJ]4949. 균형잡힌 세상  (0) 2019.07.17

문제:

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

입력:

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

출력:

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

풀이 방법:

양방향으로 이동가능이 하므로 2중배열로 만들어서 경로를 저장했다. 인덱스가 출발하는 정점이고 그 안에 들어있는 값들은 도착하는 정점이다.
DFS는 지금 마지막으로 들어온 정점이 중요하므로 그 정점이 가지고 있는 경로 중에 지나지 않은 곳으로 다시 들어가는 재귀방식으로 짜주면 된다.
BFS는 계속해서 배열을 누적하는 방식으로 진행했다. BFS에 계속 담아두고 반복문으로 하나하나 탐색하며 방문하지 않은 정점으로 이동하는 방식으로 진행했다. BFS에는 예외처리 구문이 들어가 있다. 왜냐하면 처음에는 없이 했더니 런타임에러가 발생하게 되었고, 그 이유를 알아보니 시작하는 정점이 1이라고 줬지만 1로 시작하는 정점이 없을 때 문제가 발생했다. 따라서 이 문제를 해결하기 위해 예외처리구문을 넣었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
n,m,V=map(int,input().split())
path=[[]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    if not a in path[b]:
        path[b].append(a)
    if not b in path[a]:
        path[a].append(b)
for p in path:
    p.sort()
 
DFS=[]
def dfs(now):
    DFS.append(now)
    for i in path[now]:
        if i in DFS:
            continue
        dfs(i)
    return
dfs(V)
print(*DFS)
def bfs(now):
    global BFS
    temp=[]
    if len(now)==n:
        return
    try:
        for i in now:
            for j in path[i]:
                if not j in BFS:
                    BFS.append(j)
        bfs(BFS)
    except:
        return
    return
BFS=[V]
bfs(BFS)
print(*BFS)
cs


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

[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙  (0) 2019.07.21
[BOJ]2606. 바이러스  (0) 2019.07.20
[BOJ]2164. 카드2  (0) 2019.07.18
[BOJ]4949. 균형잡힌 세상  (0) 2019.07.17
[BOJ]2004. 조합 0의 개수  (0) 2019.07.16

+ Recent posts