마쏘's 개발 성장기

Ch5. DFS/BFS

1. 꼭 필요한 자료구조 기초

    - '탐색'
      : 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 대표적인 알고리즘으로 DFS, BFS가 있다.

    - '자료구조'

      : 데이터를 표현하고 관리하고 처리하기 위한 구조

        - 오버플로(overflow) : 특정한 자료구조에 수용할 수 있는 데이터가 가득 찬 상태에서 삽입 연산을 수행할 때 발생

        - 언더플로(underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 깨 발생

    1-1. 스택

          - 선입후출 FILO or 후입선출 LIFO 구조

    1-2. 큐

          - FIFO 구조

          - deque 자료구조를 활용하자. 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에

            비해 효율적이고 queue 라이브러리를 사용하는 것보다 더 간단하다.

    1-3. 재귀 함수

          - 자기 자신을 다시 호출하는 함수

          - 보통 파이썬 인터프리터는 호출 횟수 제한이 있다.

          - '재귀 함수의 종료 조건'이 꼭 필요하다.

          - 내부적으로 스택 자료구조와 동일하다. 따라서 스택 자료구조를 사용해야 하는 많은 알고리즘은 재귀 함수를 이용하여
            간편하게 구현될 수 있다.

          - 재귀함수가 수학의 점화식(재귀식)을 그대로 옮겼기 때문에 재귀 함수의 코드가 더 간결하다.

            * 수학의 점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.

2. 탐색 알고리즘 DFS/BFS

    2-1. DFS

          - 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

          - 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

          - '그래프'
            : 프로그래밍에서 크게 2가지 방식으로 표현할 수 있는데 1) 인접 행렬, 2) 인접 리스트이다.

              1) 인접 행렬(Adjacency Matrix) :  2차원 배열로 그래프의 연결 관계를 표현하는 방식

                 - 연결이 되어 있지 않은 노드끼리는 비용이 무한으로 999999999 등의 큰 값으로 초기화한다.

              2) 인접 리스트(Adjacency List) : list로 그래프의 연결 관계를 표현하는 방식
                 - 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

              3)인접 행렬 vs 인접 리스트

                 : 메모리 측면에서는 인접 행렬이 낭비되고, 속도 측면에서는 인접 리스트가 느리다.

    2-2. BFS

          - 너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다.

          - 큐를 이용하면 선입선출이 되기에 자연스럽게 가까운 노드부터 탐색을 할 수 있다.

    2-3. DFS vs BFS
          - 둘 다 탐색을 수행하는데 O(N)의 시간이 소요된다. 컴퓨터 시스템의 특성상 DFS보다 BFS가 좀 빠르다.

3. 음료수 얼려 먹기

   - 문제

   - 문제 해결

     : 0인 지점에서 주변 상하좌우를 DFS로 방문하면 된다.

   - 소스 코드

n, m = map(int, input().split())

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

def dfs(x, y):
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  
  if ice_box[x][y] == 0:
    ice_box[x][y] = 1
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x+1,y)
    dfs(x,y-1)
    return True
  return False

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i,j) == True:
      result += 1

print(result)

#include <stdio.h>
using namespace std;

int N, M;
int ice_box[1000][1000];

bool dfs(int x, int y){
	if(x <= -1 || x >= N || y <= -1 || y >= M)
		return false;
	if(ice_box[x][y] == 0){
		ice_box[x][y] = 1;
		dfs(x - 1, y);
		dfs(x, y + 1);
		dfs(x + 1, y);
		dfs(x, y - 1);
		return true;
	}
	return false;
}

int main() {
    scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%1d", &ice_box[i][j]);
	}
	int result = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if(dfs(i,j) == true)
				result += 1;
		}
	}
	printf("%d\n", result);
    return 0;
}

4. 미로 탈출

   - 문제

   - 문제 해결

     : 시작 지점에서 가장 가까운 노드를 차례대로 탐색하는 BFS로 풀면 된다.

   - 소스 코드

from collections import deque

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

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

def bfs(x,y):
  que = deque()
  que.append((x,y))
  
  while que:
    x, y = que.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

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

print(bfs(0,0))

#include <stdio.h>
#include <queue>
using namespace std;

int N, M;
int miro[201][201];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs(int x, int y){
	queue<pair<int, int>> que;
	que.push({x, y});

	while(!que.empty()){
		int x = que.front().first;
		int y = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if(miro[nx][ny] == 0) continue;
			if(miro[nx][ny] == 1) {
				miro[nx][ny] = miro[x][y] + 1;
				que.push({nx, ny});
			}
		}
	}
	return miro[N-1][M-1];
}

int main() {
    scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%1d", &miro[i][j]);
	}
	printf("%d\n", bfs(0,0));
    return 0;
}

Ch4. 구현 implementation

1. 아이디어를 코드로 바꾸는 구현

      1-1. 피지컬로 승부하기

             - '코딩 테스트에서 구현이란?'

                : 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
                  그렇기 때문에 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩 테스트에서는 자주 출제가 된다.

             - '피지컬이 좋다'
               : 프로그래밍 문법을 정확하게 숙지하고, 라이브러리 사용 경험이 풍부하며, 코드 작성 속도(타자)가 빠를 때 

             - '구현 유형의 문제'
               : 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제
                 (알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 것이 좋다)

                  1) 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

                  2) 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형             

      1-2. 구현 시 고려해야 할 메모리 제약 사항

             - '변수의 표현 범위'

                1) C/C++/Java
                    : int형, long long형, BigInteger 순으로 자료형의 표현 범위에 주의해야한다.

                2) Python
                    :  직접 자료형을 지정할 필요가 없고 매우 큰 수의 연산 또한 지원하므로 주의하지 않아도 된다.

             - '파이썬에서 리스트 크기'

                 : 파이썬에서 리스트를 이용할 때 코딩 테스트의 메모리 제한을 고려해야 한다. (그러나, 드물다)

      1-3. 채점 환경

             - 시간 제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의

               알고리즘을 이용하여 풀어야 한다. N = 1,000,000(100만) -> NlogN = 약 20,000,000(2000만번)

               (제출한 코드가 1초에 2000만번의 연산을 수행한다고 가정하면 크게 무리가 없다)

             - 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의

               알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

      1-4. 구현 문제에 접근하는 방법

             - 특징
               1) 문제의 길이가 길지만, 고차원적인 사고력을 요구하지 않기 때문에 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

               2) 문자열을 처리하거나 큰 정수를 처리하는 구현 문제가 나올 때는 C/C++/Java보다 Python이 쉬울 수 있다.

      1-5. 상하좌우

             - 문제

             - 문제 해결
                : 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 이동 횟수가 N번인 경우 시간 복잡도 O(N)이다.
                  일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 simulation 유형으로 분류되며 구현이 중요한 문제다.

             - 소스 코드

      1-6. 시각

             - 문제

             - 문제 해결

               : 00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우의 수는 86,400가지(24*60*60초)이다.

                 경우의 수가 100,000가지도 되지 않기 때문에 시간 제한 2초 안에 문제를 해결할 수 있다.

                 가능한 경우의 수를 모두 검사하는 방법으로 완전 탐색 유형이다.

                 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

             - 소스 코드

2. 왕실의 나이트

    - 문제

    - 문제 해결

       : 나이트가 위치한 곳을 문자열과 숫자의 조합이 아니라 같은 행과 열 형태로 들어올 수도 있었다. (예외처리 필요)

         이 문제는 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면서 결과를 확인하면 된다. 

         나이트가 이동할 수 있는 경로는 2가지이다.

          1) 수평으로 두 칸 이동 후 수직으로 한 칸 이동

          2) 수직으로 두 칸 이동 후 수평으로 한 칸 이동

가능한 움직임을 (x,y) 나타내면 (-1, -2), (1, -2), (-1, 2), (1, 2), (-2, -1), (2, -1), (-2, 1), (2, 1)로 8가지의 경우가 나온다.

상하좌우와 비슷한 문제지만 이동방향을 dx,dy를 사용하느냐,
특정 방향 값을 지정하여 방향을 설정하느냐 2가지 모두 자주 사용되므로 참고!

    - 소스 코드

3. 게임 개발

    - 문제 

    - 문제 해결

      :  문제가 길고 문제를 바르게 이해하여 소스 코드로 옮기는 과정이 간단하지 않기 때문에 반복적인 숙달이 필요하다.

    - 소스 코드

n, m = map(int, input().split())
visit = [[0] * m for _ in range(n)]

x, y, direction = map(int, input().split())
visit[x][y] = 1

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

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

def turn_left():
  global direction
  direction -= 1
  if direction == -1:
    direction = 3

count = 1;
turn_time = 0
while True:
  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]

  if visit[nx][ny] == 0 and arr[nx][ny] == 0:
    visit[nx][ny] = 1
    x = nx
    y = ny
    count += 1
    turn_time = 0
    continue
  else:
    turn_time += 1
  
  if turn_time == 4:
    nx = x - dx[direction]
    ny = y - dy[direction]
    if arr[nx][ny] == 0:
      x = nx
      y = ny
    else:
      break
    turn_time = 0

print(count)

#include <stdio.h>
using namespace std;

int N, M, x, y, dir;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int arr[51][51];
int visit[51][51];

void turn_left() {
    dir -= 1;
    if (dir == -1) dir = 3;
}

int main() {
    scanf("%d %d", &N, &M);
    scanf("%d %d %d", &x, &y, &dir);
    visit[x][y] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            scanf("%d", &arr[i][j]);
    }
    int count = 1;
    int turn_cnt = 0;
    while (true) {
        turn_left();
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (visit[nx][ny] == 0 && arr[nx][ny] == 0) {
            visit[nx][ny] = 1;
            x = nx; y = ny;
            count += 1; turn_cnt = 0;
            continue;
        }
        else turn_cnt += 1;

        if (turn_cnt == 4) {
            nx = x - dx[dir];
            ny = y - dy[dir];
            if (arr[nx][ny] == 0) {
                x = nx; y = ny;
            }
            else break;
            turn_cnt = 0;
        }
    }

    printf("%d", count);
    return 0;
}