Skip to content

Latest commit

 

History

History
536 lines (342 loc) · 13.7 KB

_백준_강의_연습(5)_그래프.md

File metadata and controls

536 lines (342 loc) · 13.7 KB

16929번: Two Dots

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자. (점 k개로 이루어진 사이클에서 k >= 4)

모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

# 처음 나의 시도 (실패) -> 가장 최소 사이클인 4개 짜리만 정답 가능

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

c = [[False]*m for _ in range(n)]


def go(n, m):
    for i in range(0, n-1):
        for j in range(0, m-1):
            if c[i][j] == False:
                if a[i][j] != a[i][j+1]:
                    c[i][j] == True
                    if j == m-2:
                        c[i][j+1] = True

                else:
                    if a[i][j+1] == a[i+1][j+1] and a[i+1][j+1] == a[i+1][j]:
                        return "Yes"


    return "No"

go(n, m)
4 4
YYYR
BYBY
BBBY
BBBY





'Yes'

## 16929번: Two Dots
#### 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자. (점 k개로 이루어진 사이클에서 k >= 4)
#### 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

# 이전 칸과 다른 칸으로 연속해서 이동했을 때, 이미 방문한 칸(px, py)을 방문했으면 사이클이 존재한다고 볼수 있다 !

import sys


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



check = [[False]*m for _ in range(n)]

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


def go(x, y, px, py, color):
    # (종료 조건)
    if check[x][y] == True: # 이미 방문한 칸을 다시 방문한다면,
        return True # True로 종료

    # (다음 재귀 진행)
    check[x][y] = True
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        if 0<=nx<n and 0<=ny<m: # 범위 설정
            if (nx, ny) == (px, py):
                continue # 바로 전 단계에서 방문했던 이전 정점이면 pass

            if a[nx][ny] == color:
                if go(nx, ny, x, y, color): # color는 그대로
                    return True


    return False # 끝까지 True 안 나오면 False


for i in range(n):
    for j in range(m):
        if check[i][j]==True:
            continue

        ok = go(i, j, -1, -1, a[i][j])
        if ok == True:
            print('Yes')
            ##exit()
            sys.exit()

print('No')
3 4
AAAA
ABCA
AAAA
Yes



An exception has occurred, use %tb to see the full traceback.


SystemExit



/usr/local/lib/python3.7/dist-packages/IPython/core/interactiveshell.py:2890: UserWarning: To exit: use 'exit', 'quit', or Ctrl-D.
  warn("To exit: use 'exit', 'quit', or Ctrl-D.", stacklevel=1)

print(check) # 예 1) 같은 알파벳(색상) 가지는 사이클 내에서, '새로 방문하려고 하는 정점'이 '이미 방문했던 정점' 이 된다면 -> "Yes"
[[True, True, True, True], [True, False, False, True], [True, True, True, True]]

# 예제 2
"""
3 4
AAAA
ABCA
AADA
No
"""

print(check) # 예2) 모든 경로는 다 방문해도 없을 시 -> "No" 출력
[[True, True, True, True], [True, True, True, True], [True, True, True, True]]

# 이전 칸과 다른 칸으로 연속해서 이동했을 때, 이미 방문한 칸(px, py)을 방문했으면 사이클이 존재한다고 볼수 있다 !

import sys


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



check = [[False]*m for _ in range(n)]

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


def go(x, y, px, py, color):
    # (종료 조건)
    if check[x][y] == True: # 이미 방문한 칸을 다시 방문한다면,
        #print(x, y, px, py)
        return True # True로 종료

    # (다음 재귀 진행)
    check[x][y] = True
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        if 0<=nx<n and 0<=ny<m: # 범위 설정
            if (nx, ny) == (px, py):
                continue # 바로 전 단계에서 방문했던 이전 정점이면 pass

            if a[nx][ny] == color:
                if go(nx, ny, x, y, color): # color는 그대로
                    return True


    return False # 끝까지 True 안 나오면 False


for i in range(n):
    for j in range(m):
        if check[i][j]==True:
            continue

        ok = go(i, j, -1, -1, a[i][j])
        if ok == True:
            print('Yes')
            ##exit()
            sys.exit()

print('No')
3 4
AAAA
ABCA
AAAA
0 0 1 0
Yes



An exception has occurred, use %tb to see the full traceback.


SystemExit



/usr/local/lib/python3.7/dist-packages/IPython/core/interactiveshell.py:2890: UserWarning: To exit: use 'exit', 'quit', or Ctrl-D.
  warn("To exit: use 'exit', 'quit', or Ctrl-D.", stacklevel=1)

16947번: 서울 지하철 2호선

순환선(사이클 O)과 지선(트리, 사이클 X)으로 이뤄진 양방향 그래프에서 각 역과 순환선 사이의 거리를 구하라.

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

## 16947번: 서울 지하철 2호선
#### 순환선(사이클 O)과 지선(트리, 사이클 X)으로 이뤄진 양방향 그래프에서 각 역과 순환선 사이의 거리를 구하라.
#### 총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.



import sys
sys.setrecursionlimit(1000000)
from collections import deque

n = int(input())
a = [[] for _ in range(n)]

# 그래프 만들기
for _ in range(n):
    u, v = map(int, input().split())
    u -=1
    v -=1

    a[u].append(v)
    a[v].append(u)


check = [0]*n # 방문여부 파악 및 사이클 찾기를 위한 check 배열
## 0: 아직 방문하지 않음, 1: 방문함, 2: 방문 후 "사이클"의 구성요소임을 확인함


def go(x, p): # x: 현재 방문하는 정점, p: 이전 정점
    ## 리턴값의 의미
    ## -2: 사이클은 찾았으나, 포함되지 않음
    ## -1: 사이클을 찾지 못함
    ## 0~n-1: 사이클을 찾았고, 그때의 시작 인덱스

    if check[x] == 1: # 이미 방문했다면, 그 정점 리턴
        return x

    check[x] = 1 # (현재 정점 일단 방문 표시)

    for y in a[x]:
        if y == p: # 인접한 두 정점끼리는 사이클이 존재할 수 없으니까
            continue # Pass


        res = go(y, x) # 새로운 인접노드를 현재정점, 현재 노드를 이전정점으로 바꾸어 재귀 결과값 임시 저장
        
        if res == -2: ## 1)사이클을 찾은 경우 -> 종료
            return -2

        if res >= 0: ## 2) 그 외 (사이클은 찾았으나, 아직 모두 표시하지 못한 경우)
            check[x] = 2 # (사이클 구성요소임을 일단 표시)
            if x == res: ## 리턴 되다가 시작점을 찾았다면, 그 앞부터는 사이클에 포함되지 않으니
                return -2 ## -2 리턴

            else: ## 그 외 (아직은 중간과정)
                return res ## 시작 정점의 번호 리턴해주어서 -> 사이클을 찾게 함


    return -1 # 위 경우에 한번도 해당 되지 않았으면, 사이클이 없음을 출력

        
go(0, -1)


q = deque()
dist = [-1]*n # 답안 저장할 배열

for i in range(n):
    if check[i] == 2: ## i번 정점이 사이클에 해당된다면,
        dist[i] = 0 # 출력 거리는 0
        q.append(i) # 방문할 큐에 추가

    else:
        dist[i] = -1 ## i번 정점이 사이클에 해당 안되면, 거리는 일단 -1

#### BFS ####
while q:
    x = q.popleft()
    for y in a[x]:
        if dist[y] == -1: ## 아직 사이클을 찾지 못했다면,
            q.append(y) # 방문할 큐에 추가
            dist[y] = dist[x]+1 # 현재 인접정점의 출력거리는 +1 역 추가



print(*dist, sep=' ')
6
1 2
3 4
6 4
2 3
1 3
3 5
0 0 0 1 1 2

12946번: 육각보드

N × N인 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오. (1 ≤ N ≤ 50)

## 12946번: 육각보드
#### N × N인 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.
#### 어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오. (1 ≤ N ≤ 50)


# 답은 0, 1, 2, 3 가지 중 하나
# 1) 색칠해야 하는 칸이 하나도 없으면 0가지
# 2) 색칠해야 하는 칸이 모든 변을 공유하지 않으면 정답은 1가지
# 3) 이분 그래프에 해당 되면 2가지
# 4) 이분 그래프에 해당 되지 않으면 3가지


import sys
sys.setrecursionlimit(1000000)


n = int(input())
a = [input() for _ in range(n)]

color = [[-1]*n for _ in range(n)] # 방문여부 파악 및 2가지 색깔 저장 ("이분그래프"인지 파악)

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

ans = 0

#### 이분그래프 여부 파악하는 DFS ####
def dfs(x, y, c):
    global ans
    color[x][y] = c

    ans = max(ans, 1) # 색의 최소가 0일 때 방지하는 코드
    
    for k in range(6):
        nx, ny = x+dx[k], y+dy[k]
        if 0<= nx <n and 0<= ny <n: # 인접 좌표가 NxN 범위 내에 있고
            if a[nx][ny] == 'X': # 문제에서 주어진 색칠해야하는 칸에 해당될 때
                if color[nx][ny] == -1: # 아직 방문한 적 없다면
                    dfs(nx, ny, 1-c)

                ans = max(ans, 2)
                if color[nx][ny] == c: # 인접행렬이 이미 현재 색깔 c와 같은 색 => 인접행렬 불가능 => 정답은 3
                    ans = max(ans, 3)




for i in range(n):
    for j in range(n):
        if a[i][j] == 'X' and color[i][j] == -1: # (i,j) 좌표가 색칠해야 하는 칸에 해당되고 & 아직 방문한 적 없으면
            dfs(i, j, 0) # dfs 실행하여 이분그래프에 해당되는지(정답 2)/아닌지 파악(정답 3)

print(ans)
4
-X--
---X
----
-X--
1

16940번: BFS 스페셜 저지

트리와 1번 정점에서 시작한 BFS의 결과가 주어졌을 때, 이 탐색 결과가 올바른 것이면 1, 아니면 0을 출력

## 16940번: BFS 스페셜 저지
#### 트리와 1번 정점에서 시작한 BFS의 결과가 주어졌을 때, 이 탐색 결과가 올바른 것이면 1, 아니면 0을 출력

from collections import deque

n = int(input())
a = [[] for _ in range(n)]

for _ in range(n-1): # 입력으로 주어진 (n-1)개의 간선 정보
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    a[u].append(v)
    a[v].append(u)

b = list(map(int, input().split())) ## 입력으로 주어진 올바른 BFS 방문 순서인지 파악해야 하는 순서 정보
b = [x-1 for x in b]


order = [0] * n
for i in range(n):
    order[b[i]] = i ## 인덱스 대소관계를 정렬에 활용하기 이해 정점 별 주어진 인덱스 저장

for i in range(n):
    a[i].sort(key = lambda x: order[x]) ## 입력으로 주어진 순서를 기준으로 '인접리스트'를 정렬



#### BFS ####
bfs_order = [] ## BFS 결과 순서 담을 배열
q = deque()
check = [False]*n

q.append(0) # 시작 정점은 1번 노드
check[0] = True


while q:
    x = q.popleft()
    bfs_order.append(x) # 배열에도 담기

    for y in a[x]:
        if check[y] == False: # 아직 방문 안했다면
            check[y] = True # (1)방문여부 체크하고
            q.append(y) # (2)방문할 큐에 추가


# 답 출력
ok = True
for i in range(n):
    if bfs_order[i] != b[i]:
        ok = False
        break

print(1 if ok==True else 0)
4
1 2
1 3
2 4
1 2 3 4
1

16964번: DFS 스페셜 저지

트리와 1번 정점에서 시작한 DFS의 결과가 주어졌을 때, 이 탐색 결과가 올바른 것이면 1, 아니면 0을 출력

# 16964번: DFS 스페셜 저지
#### 트리와 1번 정점에서 시작한 DFS의 결과가 주어졌을 때, 이 탐색 결과가 올바른 것이면 1, 아니면 0을 출력#


n = int(input())
a = [[] for _ in range(n)]

for _ in range(n-1): # 입력으로 주어진 (n-1)개의 간선 정보
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    a[u].append(v)
    a[v].append(u)

b = list(map(int, input().split())) ## 입력으로 주어진 올바른 BFS 방문 순서인지 파악해야 하는 순서 정보
b = [x-1 for x in b]


order = [0] * n
for i in range(n):
    order[b[i]] = i ## 인덱스 대소관계를 정렬에 활용하기 이해 정점 별 주어진 인덱스 저장

for i in range(n):
    a[i].sort(key = lambda x: order[x]) ## 입력으로 주어진 순서를 기준으로 '인접리스트'를 정렬



#### DFS ####
dfs_order = [] ## DFS 결과 순서 담을 배열
check = [False]*n

def dfs(x):
    global check
    check[x] = True
    dfs_order.append(x) # 배열에도 담기

    for y in a[x]:
        if check[y] == False: # 아직 방문 안했다면
            dfs(y) # 다음 재귀 진행


dfs(0) # 시작 정점은 1번 노드


# 답 출력
ok = True
for i in range(n):
    if dfs_order[i] != b[i]:
        ok = False
        break

print(1 if ok==True else 0)
4
1 2
1 3
2 4
1 2 3 4
0