bright

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(x,y):
            if x < 0 or y < 0 or x>= len(grid) or y>= len(grid[0]) : 
                return False 
            
            if grid[x][y] == "1" :
                grid[x][y] = 0 
                
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y+1)
                dfs(x,y-1)
                
                return True
            return False 
        
        cnt = 0 
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if dfs(x,y) == True:
                    cnt += 1 
        return cnt

음료수 얼려 먹기 문제와 거의 유사한 dfs 문제이다. 

입력 받는 방식이 조금 특이하다. 

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

leetcode.com/problems/number-of-islands/

from collections import deque

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

# 상 하 좌 우  x 가 세로 y 가 가로 
dx = [ -1, 1 , 0 , 0 ]
dy = [  0, 0, -1,  1 ] 

def bfs( x, y ) : 
  queue = deque()
  queue.append((x,y))

  while queue:
    x, y = queue.popleft()

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

      if nx < 0 or ny < 0 or nx >= n or ny >= m : 
        continue 
      
      if graph[nx][ny] == 0 : 
        continue 
      
      if graph[nx][ny] == 1 : 
        graph[nx][ny] = graph[x][y] +1 
        queue.append((nx,ny))
  
  return graph[n-1][m-1]

print( bfs(0,0) )

1. 해결 : 그래프의 최단거리를 찾는 문제는 보통 bfs 를 사용해서 푼다. 

2. point : 

- bfs 를 사용할 것이므로 큐를 이용해서 구현한다. 효율성을 위해 deque 를 선언하고 사용했다. 

- 차례대로 큐에 집어 넣고 그 와 가까운 노드들을 방문하여 처리한다는 느낌으로 이해한다. 

www.acmicpc.net/problem/2178

1. 표준 라이브러리 

특정한 프로그래밍 언어에서 자주 사용되는 표준 소스 코드를 미리 구현해 놓은 라이브러리 

docs.python.org/ko/3/library/index.html

2. 내장함수 

- sum()

- print()

- min()

- max()

- eval()  : 수식이 문자열 형식으로 들어오면 계산해서 결과를 반환 

- sorted() 

3. itertools 

- permutations() :  순열 계산 ( 순서 신경 o ) 

- combinations() :  조합 계산 ( 순서 신경 x ) 

4. heapq 

python 에서 heap 기능을 위해 사용한다. 다익스트라 최단 경로 알고리즘 등에서 우선순위 큐를 구현하고자 할 때 사용된다. 파이썬에서는 힙을 최소 힙으로만 구성함을 기억한다. ( 최대 힙으로 만들고 싶으면 파라미터에 - 를 붙여 활용 ) 

- heapq.heappush() : 힙에 원소 삽입 

- heapq.heappop()  : 힙에서 원소 꺼냄 

5. bisect 

이진탐색을 쉽게 구현할 수 있도록 제공되는 라이브러리로, 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. 

- bisect_left (a, x )  :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 왼쪽 인덱스를 찾아줌. 

- bisect_right(a, x ) :  정렬된 순서를 유지하면서 리스트 a 에 데이터 x 를 삽입 할 수 있는 가장 오른쪽 인덱스를 찾아줌.

6. collections 

유용한 자료구조를 제공하는 표준 라이브러리

- deque   :  큐를 구현하는데 사용함. popleft, pop, appendleft, append 로 원소 배치. 

- Counter :  등장 횟수를 세는 기능을 제공. 리스트 같은 iterable 객체에서 원소가 몇 번 등장했는지 알려줌. 

7. math

자주 사용되는 수학적인 기능을 포함하는 라이브러리

- factorial()

- sqrt()   : 제곱근 

- gcd()   : 최대 공약수 

- pi 

- e 

1. 개념 

식별자 없이 실행 가능한 일회성 함수. 

def 의 함수 선언 없이도 하나의 식으로 함수를 단순하게 표현할 수 있음. 

2. 사용 예시 

1) 리스트 정렬 시, key 값으로 전달 // 정렬의 우선 순위를 부여하는 경우에 사용하면 매우 편리 

s = [ ( 'A', 1 ) , ( 'Z', 2 ) , ( 'N', 9 ) , ( 'B', 3 ), ( 'H', 3 ) ] 을  숫자 기준 내림차순 , 문자 기준 오름차순으로 정렬하시오. 

s.sort( key = lambda x: ( -x[1], x[0] ) ) 

결과 : [('N', 9), ('B', 3), ('H', 3), ('Z', 2), ('A', 1)]

문자 순으로 정렬하되, 문자가 동일한 경우에는 식별자 순으로 나열하라. 

logs = ["let1 art ","let2 own","let3 art", "let4 cat", "let5 book"]

logs.sort( key = lambda x: ( x.split()[1:] , x.split()[0] ) ) 

결과 : ['let1 art ', 'let3 art', 'let5 book', 'let4 cat', 'let2 own']

3. 주의 사항 

map, filter 등과 함께 사용하면 가독성이 매우 떨어질 수 있으므로 주의해서 사용한다. 

또한, 꼭 필요한 경우가 아닐 때는 람다 표현식 보다는 리스트 컴프리핸션이 더 많이 사용된다. 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 
        
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]
                
        return result 

쌀 때 사서 비쌀 때 팔아 가장 높은 수익을 얻는 문제.

그리디 알고리즘을 사용하여 풀면 간단하다. 

만약, 현재보다 다음 값이 오른다면 사고 판다. 

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

import sys
sys.setrecursionlimit(50000)

def dfs(y,x):

  if x <0 or y<0 or x>=m or y>=n : 
    return False 

  if graph[y][x] == 1 : 
    graph[y][x] = 0  # 방문처리 
      
    dfs(y-1,x)
    dfs(y+1,x)
    dfs(y,x-1)
    dfs(y,x+1)

    return True
  return False 
  
  

t = int(input())
t_cnt = []

for i in range(t):

  m, n, k = map(int,sys.stdin.readline().split()) # 가로 세로 배추 

  graph = [ [0]*m for i in range(n) ]

  for i in range(k):
    a, b = map(int,input().split())
    graph[b][a] = 1 
  
  cnt = 0

  for y in range(n):
    for x in range(m):
      if dfs(y,x) == True:
        cnt += 1

  t_cnt.append(cnt)


for i in t_cnt:
  print(i)

1. 풀이 : dfs 사용 

2. 유의점 :  계속 런타임 에러 나서 한참 헤맸는데 위에  import sys ; sys.setrecursionlimit(50000)   이 코드만 넣으면 바로 해결 된다. 파이썬은 기본이 재귀가 1000 으로 설정되어 있어서 그렇다고 한다. 아마 확인하는 예제 중에 재귀가 1000이 넘어가는 것이 있는 듯 하다.. 

www.acmicpc.net/problem/1012

n = int(input()) # 지도의 크기 
graph = []

for i in range(n):
  graph.append ( list(map(int,input())))

def dfs(x,y,num):

  if x <0 or y<0 or x>=n or y>=n : 
    return False 
  
  if graph[x][y] == 1 : 

    graph[x][y] = num+1

    dfs(x-1,y,num)
    dfs(x+1,y,num)
    dfs(x,y-1,num)
    dfs(x,y+1,num)

    return True 
  return False 

num = 1 
for x in range(n):
  for y in range(n):
    if dfs(x,y,num) == True:
      num += 1 

cnt_num = [0] * (num+1)

for x in range(n):
  for y in range(n): 
    if graph[x][y] != 0 :
      cnt_num[ graph[x][y] ] += 1 

total_num = cnt_num[2:num+1]
total_num.sort()

cnt  = len(total_num)
print(cnt)
for i in range(cnt):
  print(total_num[i])

참고 ) 음료수 얼려 먹기 문제 bright-code.tistory.com/78?category=423266

1. 풀이 방법 : dfs 이용 

2. 코드 설명 

dfs 를 사용하여 푼다. 

1 이면 집을 의미한다. 문제에서는 단지 번호를 1 부터 붙였지만, dfs 처리가 어려워서 나는 2 부터 붙였다. 

한 번 dfs  함수를 돌 때, 나와 붙어 있는 것들은 모두 num+1 로 바꿔 준다. 

나중에 숫자 별로 집의 수를 세어서 cnt_num 리스트에 넣어 주었고, 

위 코드에서는 0, 1 의 단지에 속한 집이 없으므로 필요한 부분만 넣은 리스트인 total_num 을 선언해 주었다. 

오름차순으로 sort 하고 길이와 값을 출력한다. 

www.acmicpc.net/problem/2667

n = int(input()) # 컴퓨터의 수 
m = int(input()) # 연결된 컴퓨터 쌍의 수 

graph = [ [] for _ in range(n+1) ]      # 컴퓨터 연결 관계를 나타낸 그래프 

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

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)

dfs(graph,1,visited)

cnt = -1
for i in range(n+1):
  if visited[i] == True :
    cnt += 1 

print(cnt)

방법 :  BFS 를 이용해서 풀이. 

유의 :  graph 를 채우는 과정에서, graph[b].append(a) 를 안했더니 틀렸다는 결과를 받았음.

www.acmicpc.net/problem/2606

=> 좀 더 간결한 풀이

n = int(input()) # 컴퓨터의 수 
k = int(input()) # 쌍의 수 

graph=[ [] for _ in range(n+1) ]
for i in range(k):
  s, e = map(int,input().split())
  graph[s].append(e)
  graph[e].append(s)

visited = [False]*(n+1)

def dfs( graph, v, visited):

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

dfs(graph,1,visited)

print(visited.count(True)-1)

# deque 이용해서 풀었는데 런타임 에러 남.. 

from collections import deque

def contact(spread): 

  while len(spread) > 0 : 

    if spread[0] == '0' :
      if spread[1] == '1' :
        spread.popleft()
        spread.popleft()
        
      else :
        print("NO") 
        return False 

    else :               # 1로 시작하는 경우 
      spread.popleft()   # 먼저 1 뺌 

      if len(spread) < 3 :  # 최소 1001 
        print("NO") 
        return False
      
      for i in range(2):   # 0 2개 빼기 
        if spread.popleft() != '0':
          print("NO") 
          return False

      # 여기 부터는 000~111 무조건 1로 끝나면 됨. 
      while len(spread) > 0 : 
        tmp = spread[0]

        if tmp == '1' : 
          if len(spread) == 1 or spread[1] == '0' : 
            spread.popleft()
            break  

        spread.popleft()    
      
      if tmp != '1' : 
        print("NO") 
        return False

  print("YES") 
  return True 

t = int(input())

data = []
for i in range(t):
  data.append( deque(input()) )

for i in range(t):
  contact(data[i])

# 정규 표현식으로 풀면 된다고 한다... 

-> 정규 표현식 공부하고 다시 도전! 

def fly():
    start, end = map(int,input().split())
    distance = end - start 

    cnt = 0 
    move = 1 
    max_move = 0 

    while max_move < distance : 
      cnt += 1 
      max_move += move 

      if cnt %2 ==0 : 
        move += 1 

    return cnt 


t = int(input())
data=[]

for i in range(t):
  data.append(fly())

for i in data:
  print (i)

※ 규칙 찾기 

1. 이동 횟수는 1, 1, 2, 2, 3, 3, .. 이런식으로 반복되어 나온다. 

2. 각 이동 횟수 별 가장 큰 값은, 다음과 같은 방식으로 구할 수 있다. 

    1 -> 1 

    2 -> 1 + 1 

    3 -> 1 + 1 + 2 

    4 -> 1 + 1 + 2 + 2 

    5 -> 1 + 1 + 2 + 2 + 3 

※ 코드 설명 

나의 이동 거리가 전 이동 횟수의 가장 큰 값보다 크고,  현재 이동 횟수 별 가장 큰 값보다 작으면, 현재 이동 횟수의 값을 가짐을 이용. 

현재 이동 횟수의 가장 큰 값은, 숫자를 2번 씩 더해가므로 [ cnt % 2 == 0 ] 인 경우 마다 move 값을 1 씩 올려 주었다. 

www.acmicpc.net/problem/1011