[최단경로+구현] 3문제

조은지·2021년 9월 17일

1. 뱀

링크 - https://www.acmicpc.net/problem/3190

아이디어

문제에 있는 규칙을 잘 따라준다.
deque를 사용하여 뱀의 위치를 저장한다.

사과가 있으면 1, 없으면 0, 뱀이 있으면 2로 정했다.

while문을 돌면서 time이란 변수에 1을 더해주어 시간을 구했다.

먼저 머리의 위치를 이동시키고
1. 머리가 벽의 위치보다 크거나 몸이랑 부딪힌다면?
-> 종료
2. 아니라면?
2-1. 사과가 있는 경우: 머리에 이동표시 하고, 꼬리는 그대로
2-2. 사과가 없는 경우: 머리에 이동표시 하고, 꼬리 이동 (이전 꼬리 위치의 값을 0으로 바꿈)

코드

n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보

# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break
        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1
        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1
    return time

print(simulate())

요것은 사실 내 코드가 아니라 책에 나온 모범답안이다...

풀긴 했지만
조건을 벽에 부딪히거나, 뱀의 몸통이 있는 경우를 한 번에 처리해도 되는데 나는 그걸 따로 해서 풀어줘서 코드가 더러웠고,,,
방향 돌리는 부분을 정말 드럽게 풀어서 모범답안을 올린다... 다음에 다시 풀어봐야겠다.

2. 플로이드

링크 - https://www.acmicpc.net/problem/11404

코드

INF = int(1e9) #무한 값 설정

n = int(input()) #노드의 수
m = int(input()) #간선의 수 

graph = [[INF]*(n+1) for i in range(n+1)] #2차원 리스트를 만들고 모든 값을 INF로 초기화

#자기 자신으로 가는 비용은 0으로 초기화
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            graph[i][j] = 0

#간선과 비용 입력받기
for i in range(m):
    s,e,dist = map(int,input().split())
    if graph[s][e]>dist:
        graph[s][e] = dist #경로가 여러개인 경우 작은 값을 선택

#플로이드 워셜 실행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])
            

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j]==INF:
            print("0", end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

플로이드 워셜 알고리즘을 구현하면 되는 문제. 이 때, 같은 출발지, 목적지를 가지더라도 다른 비용을 가진 경로가 입력될 수도 있었다. -> 최솟값만 저장하도록 함

3. 맥주 마시면서 걸어가기

아이디어

플로이드 워셜 카테고리에 있어서 플로이드로 풀었다.

50m 마다 맥주를 한 병씩 마시는데 20개를 가지고 있다고 하니까 최대 1000m를 움직일 수 있다.
~~(그만 마시세요)~~

좌표 조건이 -32768<=x,y<=32767 이므로 (x,y)크기를 가진 그래프를 만들면 무조건 오류가 난다.

=> 좌표 리스트 따로, 입력개수만큼의 그래프 리스트를 따로 만들어준다.

입력을 받고, graph를 초기화 해줄 때
1000m이내에 있다면 graph에 1을 표시해줌

	start	편의점1	편의점2	도착지
start	0	1	INF	INF
편의점1	1	0	1	INF
편의점2	INF	1	0	1
도착지	INF	INF	1	0

예시1번으로 풀어보면 이런 모양의 대칭 행렬이 나온다.
그 후 플로이드 실행~

코드

import sys

input = sys.stdin.readline
INF=int(1e9)


#테스트 케이스 개수 입력
t = int(input())

for i in range(t):
    n = int(input()) #편의점 개수
    location = [list(map(int,input().split())) for j in range(n+2)]
    graph=[[INF]*(n+2) for i in range(n+2)]
    
    for i in range(n+2):
        for j in range(n+2):
            if i==j:
                graph[i][j]=0
                continue
            if abs(location[i][0]-location[j][0])+abs(location[i][1]-location[j][1])<=1000:
                graph[i][j]=1 #1000m 내에 있다면 경유할 수 있음

    for k in range(n+2):
        for a in range(n+2):
            for b in range(n+2):
                graph[a][b]= min(graph[a][b],graph[a][k]+graph[k][b])
    
    if graph[0][n+1]==INF:
        print("sad")
    else:
        print("happy")

특정 좌표만 주어진 문제여서 처음에 어떻게 해야할 지 고민했다.
python3으로 하면 시간초과가 나고 ㄱ- pypy3으로 하면 통과를 했다.

코드2

import sys
from collections import deque

input = sys.stdin.readline
t = int(input())

def bfs(start):
    q= deque()
    visited=[False]*(n+1)
    q.append(start) #출발지 먼저 넣어준다
    
    while q:
        x,y = q.popleft()
        if x==dest[0] and y==dest[1]:
            print("happy") #도착하면 happy~
            return
        for idx, location in enumerate(store): 
            if visited[idx]==False:
                if abs(location[0]-x)+abs(location[1]-y)<=1000:
                    visited[idx]=True
                    q.append(location)
    print("sad")
    return

for i in range(t):
    n = int(input()) #편의점 개수
    #출발지, 편의점+도착, 도착지
    start = list(map(int,input().split()))
    store = [list(map(int,input().split())) for i in range(n+1)]
    dest = store[-1]
    bfs(start)