oneway's history

https://www.acmicpc.net/problem/14567

이거 위상정렬 문제 맞나 의심이 돼서 DFS 비슷하게 풀어봤는데 택도없이 시간초과났다.

바로 어제 공부한게 위상정렬인데.. 막상 써먹질 못하다니 ㅠ

배운점

1. 2차원 배열로 그래프를 그리는게 아니라 collections 의 defaultdict 사용하는 방법도 있더라.

    - 근데 이거 쓰면 좀 더 느림

성공코드

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

N, M = map(int, input().split())
# graph = [[] for i in range(N+1)]
graph = defaultdict(list)
indegree = [0 for i in range(N+1)]
result = [1 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # 방향그래프 그리고 진입차수 세기
    graph[a].append(b)
    indegree[b] += 1

queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append((i, 1))  # 정점 번호, count

while queue:
    now, count = queue.popleft()
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append((i, count+1))
            result[i] = count + 1

print(" ".join(map(str, result[1:])))

# 위상정렬. 거기에 dp적인 요소를 첨가함.
# 2차원 배열 graph 말고 collections 의 defaultdict 을 사용하면 좀 더 편리 (그러나 시간은 더 늘어나더라)

괴상한 DFS로 풀었다가 실패한 코드

import sys
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
indegree = [0 for i in range(N+1)]
result = [1 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # 방향그래프 그리고 진입차수 세기
    graph[a].append(b)
    indegree[b] += 1

queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append((i, 1))  # 정점 번호, count
        while queue:
            now, count = queue.pop()
            result[now] = count if result[now] < count else result[now]
            for j in graph[now]:
                queue.append((j, count+1))

print(" ".join(map(str, result[1:])))

결과

https://www.acmicpc.net/problem/2623

도대체 어떻게 푸는거지? 감이 전혀 안잡혀서 '알고리즘 분류'를 살펴봤더니

위상정렬 이라는 알고리즘 종류가 있다는 것을 알았다.

갓 동빈나 선생님께서 유튜브에 영상으로 설명을 잘 해주신 것이 있어서

보고 공부했다.

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split(" "))
indegree = [0 for i in range(N)]
graph = [[] for i in range(N)]

for _ in range(M):
    mlist = list(map(int, input().split(" ")))
    for a, b in zip(mlist[1:], mlist[2:]):
        # 간선 그리고 진입차수 세기
        graph[a-1].append(b-1)
        indegree[b-1] += 1

result = []
queue = deque()
# 진입차수 0인거만 골라 넣기
for i in range(N):
    if indegree[i] == 0:
        queue.append(i)

# 큐가 빌 때 까지 반복
while queue:
    # 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 제거하면서 진입차수가 변경되는데, 0으로 된 녀석은 다시 큐에 넣어줌.
    now = queue.popleft()
    result.append(now + 1)
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)

# 큐가 끝났는데 진입차수가 남아있다는건 모든 정점을 돌지 못했다는 것 == 결론을 낼 수가 없음
if sum(indegree) > 0:
    print(0)
else:
    for i in result:
        print(i)

# 1 4 3 이라 하면, 3으로 가기 위해 4을 거쳐야 하고, 4로 가기위해 1을 거쳐야 함.
# 6 2 5 4 도 마찬가지로 4로 가기 위해 5를, 5로 가기 위해 2를, 2를 가기 위해 6을 거쳐야 함.
# 이러한 규칙을 만족하는 순서를 만들자.
# => 위상정렬 알고리즘 사용하기

# 위상정렬
# 1. 진입차수 (들어오는 간선의 개수)가 0인 정점을 큐에 삽입한다.
# 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. (이 때 꺼낸 순서를 result에 담음)
# 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입한다.
# 4. 큐가 빌 때 까지 2,3번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.
# 위상정렬 정보 출처: https://www.youtube.com/watch?v=qzfeVeajuyc

https://www.acmicpc.net/problem/24444

[실패] 라고 떠있길래 이걸 왜못풀었지? 싶었는데 못푼 이유가 있었다.

시간복잡도를 상당히 신경써야 하는 문제...

그냥 대충 행렬로 만들면 안됐다.

이전에 자바로 [실패] 를 엄청 많이 했길래 이걸 못풀었어? 하고 슥 풀라했다가

이번에도 [실패] 난무했다.

항상 풀던대로 visited 를 이용해줬는데,

얘를 빼고 풀어보니 통과가 됐다.

그리고 answer 리스트에 답을 담는 과정에서 불필요하게 if문이 도는걸 막았다.

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]
# visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

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

for i in range(1, N+1):
    graph[i].sort()


queue = deque()
queue.append(R)
answer[R] = 1
cnt = 2
while queue:
    num = queue.popleft()
    # visited[num] = True
    # if answer[num] == 0:
    #     answer[num] = cnt
    #     cnt += 1

    for idx in graph[num]:
        if answer[idx] == 0:  # 방문한적 없으면 고
            queue.append(idx)
            answer[idx] = cnt
            cnt += 1

for i in answer[1:]:
    print(i)

# visited 이녀석 생성하는 시간이 오래걸렸나? 
# visited 역할을 answer가 대신 하게 해줬더니 통과됐다.

https://www.acmicpc.net/problem/24479

1. 자바로 풀때처럼 리스트 형식으로 구현할라고 했는데, 정점 수가 많아서 메모리 초과가 났다.

  -> 그래서 연결된 부분만 입력받도록 append 하는거로 바꿈

  -> 오름차순 컨셉 유지하기위해 graph의 모든 부분을 오름차순함.

2. 재귀로 DFS 할라했는데, 간선이 20만개로 너무 많아서 계속 Recursion Error 남. IDE에선 잘 돌아가는데.

  -> 그래서 그냥 Stack 과 While 문으로 해결함.

  -> Stack을 쓰다보니 앞쪽부터 빼가니까 graph를 내림차순으로 바꿈

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
# graph = [[False for i in range(N+1)] for i in range(N+1)]
graph = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

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

for i in range(N+1):
    # graph[i].sort()
    graph[i].sort(reverse=True)

# print(graph)
cnt = 1


# def dfs(num):
#     visited[num] = True
#     global cnt
#     # answer[cnt] = num
#     if answer[num] == 0:
#         answer[num] = cnt
#         cnt += 1
#     for idx in range(len(graph[num])):
#         s = graph[num][idx]
#         # 간선으로 연결되어있고 이미 방문하지 않았다면
#         # if graph[num][idx] == True and visited[idx] == False:
#         if visited[s] == False:
#             dfs(s)


# dfs(R)

stack = deque()
stack.append(R)

while stack:
    num = stack.pop()
    visited[num] = True
    if answer[num] == 0:
        answer[num] = cnt
        cnt += 1

    for idx in graph[num]:
        if visited[idx] == False:
            stack.append(idx)


for i in range(1, N+1):
    print(answer[i])

# 1. 전체를 리스트로 담다보니 메모리 초과남
# 2. 재귀를 쓰려다보니 간선이 200000개가 최대라 recursion error 뜸
# 3. 스택쓰고 while 쓴다.

그래프 문제를 너무 오랜만에 풀어서 그런가 꽤나 오래걸렸다.

https://www.acmicpc.net/problem/2589

요령

1. 냅다 2차원 배열의 처음부터 끝까지 탐색하면서 "L" 인 녀석을 찾는다.

2. 그녀석부터 시작해서 BFS를 탐색하는데, 다음 칸으로 넘어갈 때마다 time 을 1씩 더해주면서 간다.

3. 매번 time이 갱신될 때마다 전역변수에 있는 result와 비교해서 최대값으로 갱신해준다.

풀면서 배운점

1. 입력받을 때, 문자 사이에 빈 칸이 없을 때 2중 for문으로 직접 append 해주었는데, 한 줄로 쓸 수 있는 방법을 배웠다.

심지어 별로 속도 차이도 안남.

(2중 for문 했을 때 820ms, 한 줄로 입력받았을 때 816ms 였다)

mmap = [[] for i in range(R)]
for i in range(R):
	s = input().rstrip()
	for j in s:
    	mmap[i].append(j)

mmap = [list(input()) for i in range(R)]

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split())
mmap = [[] for i in range(R)]
visited = [[False for i in range(C)] for i in range(R)]
result = 0
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(R):
    s = input().rstrip()
    for j in s:
        mmap[i].append(j)


def bfs():
    # print("\nbfs 시작")
    while queue:
        r, c, time = queue.popleft()
        # print(r, c, time)
        global result
        result = max(time, result)
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C or mmap[nr][nc] == "W" or tvisited[nr][nc] == True:
                continue
            queue.append((nr, nc, time+1))
            tvisited[nr][nc] = True


for r in range(R):
    for c in range(C):
        if mmap[r][c] == "L":
            queue = deque()
            queue.append((r, c, 0))
            tvisited = [m[:] for m in visited]
            tvisited[r][c] = True
            bfs()

print(result)

항상 자바로 풀다가 파이썬으로 그래프 문제를 풀어봤다.

이 문제에서 배운 점:

1. import copy 해서 2차원 배열을 deepcopy 하는 방법은 slicing 해서 복사 하는 것보다 훨씬 느리다는 점.

(deepcopy를 사용하면 3136ms, 사용하지 않으면 1676ms 가 나왔다.)

2. 자바로 풀던때가 적응돼서 visited 배열을 꼭 따로 만들어줬었는데, 그럴필요 없다는 점

3. append 할 때 [nr, nc] 처럼 리스트가 아니라 (nr, nc) 해서 튜플로 해주면 더 빠르다는점.

(리스트 썼을 때 1860ms, 튜플로 썼을 때 1676ms 가 나왔다.)

4. import time 이란걸 사용해서 꼭 백준에 제출하지 않더라도 코드 실행시간을 체크할 수 있다는 점을 알았다.

import sys
# import copy
# import time
from collections import deque
# start = time.time()
input = sys.stdin.readline
R, C = map(int, input().split())
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
mmap = []
answer = 0
for i in range(R):
    mmap.append(list(map(int, input().split())))


def bfs():
    queue = deque()
    tmap = [m[:] for m in mmap]
    # tmap = copy.deepcopy(mmap)
    for i in range(R):
        for j in range(C):
            if tmap[i][j] == 2:
                queue.append((i, j))

    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C:
                continue
            if tmap[nr][nc] == 0:
                tmap[nr][nc] = 2
                queue.append((nr, nc))

    global answer
    cnt = 0
    for i in range(R):
        cnt += tmap[i].count(0)
    answer = max(answer, cnt)


def backtrack(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(R):
        for j in range(C):
            if mmap[i][j] == 0:
                mmap[i][j] = 1
                backtrack(cnt+1)
                mmap[i][j] = 0


backtrack(0)
print(answer)
# print("time : ", time.time() - start)

https://www.acmicpc.net/problem/2583

직사각형으로 덮힌 부분을 1, 안덮힌 부분을 0 로 저장,

모든 경우를 탐색하며 0일 때 BFS 시작하여 while 이 끝날 때 pieces가 1 추가되게 해서 분리된 영역의 개수를 구했고

BFS 돌때마다 getArea를 1씩 더해주며 그 넓이를 구했습니다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_백준_2583_영역구하기_실버1_144ms {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(stk.nextToken());
		int C = Integer.parseInt(stk.nextToken());
		int K = Integer.parseInt(stk.nextToken());
		int[][] map = new int[R][C];
		for (int i = 0; i < K; i++) {
			stk = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(stk.nextToken());
			int y1 = Integer.parseInt(stk.nextToken()); // 왼쪽위
			int x2 = Integer.parseInt(stk.nextToken());
			int y2 = Integer.parseInt(stk.nextToken()); // 오른아래

			for (int j = y1; j < y2; j++) {
				for (int k = x1; k < x2; k++) {
					map[j][k] = 1;
				}
			}
		}

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };
		boolean[][] visited = new boolean[R][C];
		ArrayList<Integer> arr = new ArrayList<Integer>();
		Queue<int[]> q = new LinkedList<int[]>();
		int pieces = 0, getArea = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 0 && !visited[i][j]) {
					pieces++;
					getArea = 1;
					q.offer(new int[] { i, j });
					visited[i][j] = true;
					while (q.size() > 0) {
						int r = q.peek()[0];
						int c = q.poll()[1];
						for (int k = 0; k < 4; k++) {
							int nr = r + dr[k];
							int nc = c + dc[k];
							if (0 > nr || nr >= R || 0 > nc || nc >= C || visited[nr][nc] || map[nr][nc] == 1) {
								continue;
							}
							getArea++;
							q.offer(new int[] { nr, nc });
							visited[nr][nc] = true;
						}
					}
					arr.add(getArea);
				}
			}
		}
		System.out.println(pieces);
		Collections.sort(arr);
		for (int i = 0; i < arr.size(); i++) {
			System.out.print(arr.get(i) + " ");
		}
	} // 메인 끝
}

결과

https://www.acmicpc.net/problem/4963

섬인지 아닌지 체크하는 부분을 BFS를 이용해 visited 체크해가며 반복문을 도는 방식으로 풀어주었습니다.

시간 효율을 조금이나마? 늘리기 위해 일반 map의 행과 열의 크기를 2씩 넓게 해서 if문 사용을 줄였습니다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_백준_4963_섬의개수_실버2_188ms {
	private static int[] dr = {-1,-1,0,1,1,1,0,-1}; // 12시부터 시계방향
	private static int[] dc = {0,1,1,1,0,-1,-1,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		StringBuilder sb = new StringBuilder();
		while(true) {
			stk = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(stk.nextToken());
			int h = Integer.parseInt(stk.nextToken());
			if (w == 0 && h == 0) break;
			int[][] map = new int[h+2][w+2];
			boolean[][] visited = new boolean[h+2][w+2];
			for (int i = 1; i <= h; i++) {
				stk = new StringTokenizer(br.readLine());
				for (int j = 1; j <= w; j++) {
					map[i][j] = Integer.parseInt(stk.nextToken());
				}
			}
			
			int cnt = 0;
			Queue<int[]> q = new LinkedList<int[]>(); 
			for (int r = 1; r <= h; r++) {
				for (int c = 1; c <= w; c++) {
					if (map[r][c] == 1 && !visited[r][c]) {
						cnt++;
						q.offer(new int[] {r, c});
						while(q.size() > 0) {
							int rr = q.peek()[0];
							int cc = q.poll()[1];
							for (int i = 0; i < 8; i++) {
								int nr = rr + dr[i];
								int nc = cc + dc[i];
								if (map[nr][nc] == 1 && !visited[nr][nc]) {
									q.offer(new int[] {nr, nc});
									visited[nr][nc] = true;
								}
							}
						} // while 끝
					}
				}
			}
			sb.append(cnt).append("\n");
		} // while 끝
		System.out.println(sb);
	} // 메인 끝
}

결과