bright

import sys
sys.setrecursionlimit(10000000)

m, n, k = map(int, input().split()) # 세로 가로 직사각형 수 

# 직사각형으로 채워지면 1, 안 채워지면 0
graph = [ [0]*n for _ in range(m) ]

for i in range(k):
  s1, e1, s2, e2 = map(int,sys.stdin.readline().split())

  for x in range(s1,s2):
    for y in range(e1, e2):
      graph[y][x] = 1 

def dfs ( x, y, cnt ):
  graph[y][x] = 1 
  cnt += 1 

  move_x = [-1,1,0,0] # 가로 -> n 
  move_y = [0,0,-1,1] # 세로 -> m 

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

    if nx < 0 or ny < 0 or nx >=n or ny>=m : 
      continue 
    if not graph[ny][nx] :
      cnt = dfs(nx,ny,cnt)
  
  return cnt

area = []

for x in range(n):
  for y in range(m):
    if not graph[y][x]:
      cnt = 0 
      area.append(dfs(x,y,cnt))

print( len(area) )
area.sort()
for i in range(len(area)):
  print(area[i], end=' ')

step 1 ) 런타임 에러 방지를 위해 sys import 하고  graph 선언 

           직사각형으로 채워질 부분은 1, 채워지지 않은 부분은 0 으로 설정한다. 

step 2 ) 직사각형의 좌표값을 입력받아 graph 채우기  -> 실제로 출력해보면 거꾸로 나오긴하는데 상관 없음 

step 3 ) dfs 구현, 가로 세로로 움직이면서 연결된 영역 세기 

           각 영역별 넓이를 구해야 하므로 dfs 가 진행 될 때마다 cnt 를 세어주고 return 하는 식으로 계산한다. 

step 4 ) graph 전체를 탐색하면서 dfs 를 진행한다. 이 때 돌려 받은 cnt 의 값을 각 구역의 넓이를 저장하는 area에 저장

step 5 ) area 의 길이와, 정렬한 결과를 출력

import copy
import sys
sys.setrecursionlimit(10000000)

n = int(input())

graph = []
max_h = 0 
for i in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))
  max_h = max( max_h, max(graph[i]))

save = [0] * ( max_h +1 )
save[0] = 1  # 비가 안오면 전 영역( 1개 ) 이 안전하다.

def dfs ( x,y,h, tmp_graph):

  move_x = [-1,1,0,0] # 가로 
  move_y = [0,0,-1,1] # 세로 

  tmp_graph[x][y] = 0 

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

    if nx <0 or ny <0 or nx>=n or ny>= n : 
      continue 
    if tmp_graph[nx][ny] >= h : 
      dfs ( nx, ny, h, tmp_graph)

for h in range(1, max_h+1):
  tmp = copy.deepcopy(graph)
  cnt = 0 
  for i in range(n):
    for j in range(n):
      if tmp[i][j] >= h : 
        dfs(i,j,h,tmp)
        cnt += 1 
  save[h] = cnt 

print(max(save))

step 1 ) 그냥 입력 받으면 런타임 에러 나니까 import sys 

step 2 ) graph 입력 받기 , 가장 큰 높이 까지만 찾아보면 되니까 가장 큰 높이 구하기 

step 3 ) 각 높이 별 안전한 영역 저장할 list 선언 ( save ) 

           단, 높이가 0 일 때는 모두 다 하나의 안전한 구역이므로 1 로 설정. 

step 4 ) dfs 구현 하기. 가로 세로로 움직이며 다음과 같은 조건 부여

           ① 움직인 결과 그래프 안에 있는지  ② 현재 검사하고 있는 높이보다 높으면 dfs 진행 

            ③ 방문 처리를 위해서 dfs 진행한 구역은 값을 0으로 만들어주기 

step 5 ) 1 ~ 가장 높은 높이까지 반복.  기존 graph 는 바뀌면 안되니까 깊은 copy 를 통해 각 높이 별로 복사해서 사용 

           깊은 복사는 copy module 로 구현 가능하며,  a = copy.deepcopy( b ) 와 같이 쓴다. 

step 6 ) 각 높이 별 안전한 구역의 개수 세어서 저장, 가장 큰 값 출력하기 

import sys
sys.setrecursionlimit(10000000)

def island(w,h):

    graph = []
    for i in range(h):
      graph.append( list(map(int,sys.stdin.readline().split()))) 

    move_x = [ -1, 1, 0, 0, -1,-1,1,1 ]  # x는 세로, 순서대로 가로 세로 대각선 
    move_y = [ 0, 0, -1, 1, -1,1,-1,1 ]  # y는 가로
    
    def dfs ( x,y ) : 
        graph[x][y] = 0

        for i in range(8):
            nx = x + move_x[i]
            ny = y + move_y[i]

            if nx<0 or ny<0 or nx>=h or ny>=w :
              continue

            if graph[nx][ny] : 
              dfs( nx, ny )
              continue

    cnt = 0 

    for y in range(w):
      for x in range(h):
          if graph[x][y]:
            dfs(x,y)
            cnt += 1 
    return cnt 


p = []

while 1: 
    w, h = map(int,sys.stdin.readline().split()) # 지도 너비, 높이 <= 50 
    if w == 0 and h == 0 : 
        break 
    else:
        p.append( island(w,h) )

for i in range(len(p)):
  print(p[i])

거의 구현 문제다.. 

1. 섬과 바다 지도를 graph 에 받아오기 

2. 만약 내가 지금 방문한 노드가 섬이라면, 인접한 섬 방문하는 dfs 재귀 방법 사용 

   ( 인접한 섬을 방문하는 경우의 수는 가로 2개 세로 2개 대각선 4개하여, 총 8가지 이다. ) 

3. 한 번 탐색을 끝나면 섬 하나가 끝난 것이므로 cnt +1 

tip) 런타임 에러 해결 

-> 보토 입력값이 크고 파이썬은 조금 느린 언어다 보니까 입력하는 부분에서 런타임 에러가 발생할 수 있다. 

import sys

sys.setrecursionlimit(10000000)

w, h = map(int,sys.stdin.readline().split())

위의 코드를 통하여 해결한다. ( 모든 입력 부분에 sys.stdin.readline() 을 사용한다 )

import sys
sys.setrecursionlimit(10000000)
n, m = map(int,sys.stdin.readline().split())

graph = [ [] for i in range(n+1) ]

for i in range(m):
  start, end = map(int,sys.stdin.readline().split())

  graph[start].append(end)
  graph[end].append(start)

visited = [False] * (n+1) 

def dfs ( graph, v,visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs( graph, i, visited)


cnt = 0 

for i in range(1,n+1):
  if not visited[i] :
    cnt += 1 
    dfs( graph, i, visited)

print(cnt)

그냥 아주 기초적인 bfs 풀이와 유사하다. 

프로그래머스의 네트워크 문제와 비슷한 것 같다. 

다만, 런타임 에러가 난다면 입력 할 때 sys를 import한 다음 아래 식을 사용해서 입력 받는다. 

import sys

sys.setrecursionlimit(10000000)

n, m = map(int,sys.stdin.readline().split())

DFS 

def dfs( v, visited_dfs ):
  if not visited_dfs[v-1] :
    visited_dfs[v-1] = True
    print(v, end=' ')
    
    if v in graph.keys():
      for i in graph[v]:
          dfs( i, visited_dfs )

1. 시작 노드를 stack 에 넣고 방문 처리 

2. stack의 최 상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 stack 에 넣고 방문 처리 

   -> 최 상단 노드 중 방문하지 않은 인접 노드가 없으면 최상단 노드 pop 

3. 반복 

BFS 

def bfs( v, visited_bfs ) :
    queue = deque()
    queue.append(v)

    while queue : 
        now = queue.popleft()

        if not visited_bfs[now-1]:
          visited_bfs[now-1] = True
          print(now, end= ' ')

          if now in graph.keys():
            for i in graph[now]:
              queue.append(i)

1. 탐색 시작 노드를 큐에 넣고 방문 처리

2. 큐에서 노드를 꺼내어 해다 노드의 인접 노드 중 방문하지 않은 모든 노드를 큐에 삽입 하고 방문 처리

3. 반복 

실행 코드 

from collections import deque 

n, m, v = map(int,input().split()) # 노드, 간선, 시작점 

graph = dict()

for i in range(m):
    start, end = map(int,input().split())

    if start in graph:
        graph[start].append(end)
    else:
        graph[start] = [end] 

    if end in graph:
      graph[end].append(start)
    else:
      graph[end] = [start]

for i in graph.keys():
    graph[i].sort()

visited_dfs = [False] * n
visited_bfs = [False] * n  

dfs(v, visited_dfs)
print()
bfs(v, visited_bfs)

개념만 알면 풀 수 있는 문제일 줄 알았는데 생각보다 오래 걸렸다. 

그래프 만들 때, start-end 와 end-start  모두 넣어 주어야 하는 것에 유의하자. 

www.acmicpc.net/problem/1260

def solution(tickets):

    routes = dict()

    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    st = ['ICN']
    ans = []
    while st:
        top = st[-1]
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop())
            
        else:
            st.append(routes[top].pop())

    ans.reverse()
    return ans

... 아직 dfs-bfs 가 익숙하지 않다.  엄청 어렵다. 

step 1 ) 갈 수 있는 경로를 정의 한 routes 딕셔너리를 만든다. 

step 2 ) 문제에서 가능한 알파벳 순으로 나열하라고 했으므로 정렬한다. 이 때, 역으로 정렬하여 pop 했을 때 

           알파벳 순서가 빠른 곳이 먼저 나오도록 한다. 

step 3 ) 시작점은 'ICN' 이다. 

step 4 ) 문제에서 무조건 다 사용할 수 있다고 했으므로, 다음과 같은 알고리즘을 적용할 수 있다. 

           만약 내가 가려는 곳이 routes 에 존재하지 않는다면 ans 에 넣는다. 마지막에 다른 곳에서 이곳에 도착할 

           것이 분명하다.  존재한다면 다음 목적지로 삼으면 된다. 

Reference 

아래 블로그를 참고했음. 설명이 잘 되어있다. 

https://gurumee92.tistory.com/165

from collections import deque

def solution(begin, target, words):

    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        next_words = []

        for i in words:
            diff = 0 
            for j in range(len(begin)) :
                if i[j] != current[j]:
                    diff += 1 
            
            if diff == 1 : 
                next_words.append(i)

        for next_word in next_words:
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

1. 분류 : BFS 

2. 풀이 방법 

step 1) bfs 알고리즘을 구현하기 위하여 deque 를 사용한다. 

step 2 ) dist = { 단어 : 변환한 수 } 를 표현하는 딕셔너리 이다.  처음에 begin 을 넣고 deque 에도 begin 을 넣는다. 

step 3 ) current 는 지금 검증할 단어이다. 

           -> 만약 current 와 알파벳 1개 차이가 나는 단어가 있다면 next_words 배열에 넣는다.

step 4 ) next_words 가 전에 바뀌었던 단어가 아니라면, dist 와 queue 에 넣어 준다. 

=> 4 단계 까지 오게 되면 모든 단어 변환을 거친다. 

step 5 ) 만약 dist 에 target 이 있다면 ( 변환 가능함을 의미 ) 변환 한 수를 출력하고, 없다면 0 ( default ) 를 출력한다. 

+ tip )  딕셔너리의 get method 

딕셔너리.get( key[ , defualt 값 ] ) 

: 딕셔너리에 key 가 있으면 해당 key의 value를 반환하고, 없으면 default에 지정한 값을 반환한다. 

default 생략 시, 아무런 값도 ( None ) 반환하지 않는다. 

def dfs(graph, v, visited. n) : 
    tmp = 0 
    if not visited[v] :
        visited[v] = True
        for i in range( n ):
            if graph[v][i] :
                dfs(graph, i, visited)
                tmp += 1 
        
        if tmp >= 1 : return True
    return False

def solution(n, computers):

    visited = [False] * n
    answer = 0

    for i in range(n):
        if dfs(computers, i , visited, n ): 
            answer += 1 
    return answer

step 1) 전에 방문한 적 없으면 -> 방문 처리  / 방문한 적 있으면 바로 return False 

step 2 ) 나랑 연결된 것 중에 -> 방문한 것 없는지 찾기 / 방문한 적 없는 것이 하나도 없으면 return False . 

                                                                          하나라도 방문 하지 않은 것이 있으면 return True 

def solution(numbers, target):
    data = [0]
    for i in numbers:
        tmp = []
        for j in data : 
            tmp.append(j+i)
            tmp.append(j-i)
        data = tmp
    return data.count(target)

numbers 안의 값은 더해지거나 빼지거나 2가지 경우의 수를 갖는다. 

모든 numbers 에 대하여 각 경우의 수를 더해 나가면 모든 경우의 수를 가질 수 있다. 

programmers.co.kr/learn/courses/30/lessons/43165

import itertools

L, c = map(int,input().split()) # 암호 길이, 문자의 수 
data = list(map(str,input().split()))
data.sort()

# c 개 중에 L 개 뽑아 나열하기 
# 최소 모음 1개 최수 2개 자음 

vowel = [ 'a', 'e', 'i', 'o', 'u']

for i in itertools.combinations( data,L):

    cnt = 0 

    for k in i : 
        if k in vowel:
            cnt += 1 
    
    if cnt >= 1 and cnt <= L-2 : 
        print( ''.join( i ))

풀이 방법 : 조합 ( combination ) 사용  /  import itertools 

L 개 중, c 개의 문자를 뽑아 암호를 만든다. 문제에서 순서는 알파벳 순이라고 지정해 주었으므로 

순열 ( permutations ) 가 아닌 조합을 사용하면 된다. 

암호의 조건으로 모음이 최소 1개, 자음이 최소 2개이다. 

따라서, 우선 가능한 조합을 모두 나열한 다음,

모음을 세는 변수를 만들어 암호 안의 모음의 개수를 세고 이를 활용하여 자음의 개수 까지 센다. 

( 모음이 아닌 건 다 자음이므로 모음의 수가 ( 전체 암호 길이 ) - 2 이하라면 조건을 만족한다 )