모각코 5회차

✏️ 코테 준비 백준 풀기

Union-Find

• 여행가자 (🥉골드 4티어 )

구현

• 뱀 (🥉골드 4티어 )

1976 여행가자

---

def find(x):
    if x == parent[x]:
        return x
    else:
        return find(parent[x])

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    if v < u:
        parent[u] = v

n = int(input())
m = int(input())
graph = []
for _ in range(n):
    temp = list(map(int,input().split()))
    graph.append(temp)

route = list(map(int,input().split()))
for i in range(len(route)):
    route[i] -=1

parent = [i for i in range(n)]

for i in range(len(graph)):
    for j in range(len(graph[i])):
        if graph[i][j] == 1:
            union(i,j)

parent_first = find(route[0])

answer=True
for i in route:
    if parent_first != find(i):
        answer=False
        break

print("NO") if answer==False else print("YES")

---

3190 뱀

---

from collections import deque

N = int(input()) # n*n square
k = int(input()) # apple
graph = [[0]*N for _ in range(N)]
where = "RIGHT"
for _ in range(k):
    x,y = map(int,input().split())
    graph[x-1][y-1] = 1

L =  int(input())
change = {}
for _ in range(L):
    sec, direction = map(str,input().split())
    sec = int(sec)
    change[sec] = direction

idx = 0
q = deque()
q.append((0,0))
while(q):
    x, y = q[-1][0], q[-1][1]
    if 0<=x<N and 0<=y<N:
        if idx in change:
            if change[idx] == "L":
                if where == "RIGHT":
                    where = "UP"
                elif where == "UP":
                    where = "LEFT"
                elif where == "LEFT":
                    where = "DOWN"
                elif where == "DOWN":
                    where = "RIGHT"
            if change[idx] == "D":
                if where == "RIGHT":
                    where = "DOWN"
                elif where == "DOWN":
                    where = "LEFT"
                elif where == "LEFT":
                    where = "UP"
                elif where == "UP":
                    where = "RIGHT"
        if where == "RIGHT":
            if (x, y+1) in q:
                break
            q.append((x,y+1))
            if 0<=x<N and 0<=y+1<N:
                if graph[x][y+1] == 0:
                    q.popleft()
                else:
                    graph[x][y+1] = 0
            else:
                break
        elif where == "DOWN":
            if (x+1, y) in q:
                break
            q.append((x+1,y))
            if 0<=x+1<N and 0<=y<N:
                if graph[x+1][y] == 0:
                    q.popleft()
                else:
                    graph[x+1][y] = 0
            else:
                break
        elif where =="LEFT":
            if (x, y-1) in q:
                break
            q.append((x,y-1))
            if 0<=x<N and 0<=y-1<N:
                if graph[x][y-1] == 0:
                    q.popleft()
                else:
                    graph[x][y-1] =0
            else:
                break
        elif where == "UP":
            if (x-1, y) in q:
                break
            q.append((x-1,y))
            if 0<=x-1<N and 0<=y<N:
                if graph[x-1][y] == 0:
                    q.popleft()
                else:
                    graph[x-1][y] =0
            else:
                break
        idx +=1
    else:
        break
print(idx+1)

---