IT-garden

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력과 출력

알고리즘 분류

DFS
백트래킹

정답

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

r,c=map(int,input().split())
a=[list(map(lambda x : ord(x)-65, input())) for i in range(r)]
ch=[0] * 26 # 26은 알파벳 개수

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def dfs(x, y, z):
    global answer
    answer=max(answer, z)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and ch[a[nx][ny]] == 0:
                ch[a[nx][ny]] = 1
                dfs(nx, ny, z+1)
                ch[a[nx][ny]] = 0

answer=1
ch[a[0][0]] = 1
dfs(0, 0, answer)

print(answer)

python 시간초과로 PyPy3로 제출했습니다.

입력받은 알파벳들을 아스키 코드 값으로 바꿔 저장합니다.
해당 알파벳을 거쳤는지 확인할 리스트 ch를 이용하기 위해서입니다.

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

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2<=N<=500)과 두 학생 키를 비교한 횟수 M (0<=M<=N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

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

INF=sys.maxsize

n,m=map(int,input().split())
li=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    a, b=map(int, input().split())
    li[a][b] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                continue
            
            if li[i][k] == 1 and li[k][j] == 1:
                li[i][j] = 1

r=0
for i in range(1,n+1):
    c = 0
    for j in range(1, n+1):
        c += li[i][j] + li[j][i] 
    if c == n-1: #자기빼고 다 아는 경우
        r += 1
print(r)

시간 초과로 PyPy3로 제출했습니다.

a 학생이 b 학생보다 작으면 li[a][b]에 1을 추가합니다.

플로이드 와샬 알고리즘을 통해 k를 거쳐서 키를 확인할 수 있으면 거리를 1로 바꿔줍니다.

li[i][j] + li[j][i]을 통해 i보다 j가 크거나 작은지 확인합니다.
자신을 제외한 다른 수들이 크거나 작은지 확인할 수 있으면 r에 1을 더해주고 전체 r을 출력합니다.

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

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque

h,w=map(int,input().split())

a=[list(input()) for i in range(h)]

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
l=[]

def bfs(s):
    ch=[[0]*w for i in range(h)] 
    de=deque()
    de.append(s)
    ch[s[0]][s[1]] = 1
    ma=0
    while len(de) != 0:
        m=de.popleft()
       
        for i in range(4):
            nx = m[0] + dx[i]
            ny = m[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w:
                if a[nx][ny] == 'L' and ch[nx][ny] == 0:
                    ch[nx][ny] = ch[m[0]][m[1]] + 1
                    de.append([nx,ny])
                    ma=max(ma, ch[nx][ny])
                    
    l.append(ma-1)

for i in range(h):
    for j in range(w):
        if a[i][j] == 'L':
            bfs([i,j])
            
print(max(l))

PyPy3로 제출했습니다.

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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

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

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

def bfs(s):
    de=deque()
    de.append(s)
    ch[s]=1
    
    while de:
        x=de.popleft()

        for i in a[x]:
            if ch[i] == 0:
                ch[i] = 1
                de.append(i)

c=0

for i in range(1,n+1):
    if ch[i] == 0:
        c += 1
        bfs(i)

print(c)    

파이썬 시간초과로 PyPy3로 제출했습니다.

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