<div id="readability-page-1" class="page"><div><h2 id="문제">문제</h2>
<a href="https://www.acmicpc.net/problem/2583">영역 구하기</a>
<img src="https://velog.velcdn.com/images/dongha1992/post/0d8bb4f5-ec63-458e-926f-842f236d1cf6/image.png">
<h2 id="풀이">풀이</h2>
<ul>
<li>영역 개수 만큼 순회하며 주어진 좌표들을 기준으로 board[][]에 1을 채움</li>
<li>board를 순회하면서 dfs로 영역의 개수를 카운팅</li>
</ul>
<h2 id="코드">코드</h2>
<pre><code>import java.util.*;

public class Main {
 static int m, n, K;
 static int[][] board;
 static boolean[][] visited;
 static int[] dx = {0, 0, 1, -1}; 
 static int[] dy = {1, -1, 0, 0};
 
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 
 m = scanner.nextInt();
 n = scanner.nextInt();
 K = scanner.nextInt();
 
 board = new int[m][n];
 visited = new boolean[m][n];
 
 for(int i = 0; i &lt; K; i++){
 int startX = scanner.nextInt();
 int startY = scanner.nextInt();
 int endX = scanner.nextInt();
 int endY = scanner.nextInt();
 
 for(int j = startY; j &lt; endY; j++){
 for(int l = startX; l &lt; endX; l++){
 board[j][l] = 1;
 }
 }
 }
 
 List&lt;Integer&gt; answer = new ArrayList&lt;&gt;();
 
 for(int i = 0; i &lt; m; i++){
 for(int j = 0; j &lt; n; j++){
 if(board[i][j] == 0 &amp;&amp; !visited[i][j]){
 answer.add(dfs(i, j));
 }
 }
 }
 
 Collections.sort(answer);
 System.out.println(answer.size());
 for (int area : answer) {
 System.out.print(area + " ");
 }
 }
 
 private static int dfs(int x, int y) {
 visited[x][y] = true;
 int area = 1;
 
 for(int i = 0; i &lt; 4; i++){
 int nx = x + dx[i];
 int ny = y + dy[i];
 
 if(nx &gt;= 0 &amp;&amp; ny &gt;= 0 &amp;&amp; nx &lt; m &amp;&amp; ny &lt; n &amp;&amp; board[nx][ny] == 0 &amp;&amp; !visited[nx][ny]){
 area += dfs(nx, ny);
 }
 }
 return area;
 }
}

</code></pre>
<h2 id="정리">정리</h2>
<ul>
<li>왜 모눈종이를 뒤집었지..? 찾느라 한참 걸림.. 뭔가 문제 해석이 더 어려움..</li>
<li>수능 문제 같음</li>
</ul></div></div>

삶도 재입학이 되나요?

문제
영역 구하기
풀이
영역 개수 만큼 순회하며 주어진 좌표들을 기준으로 board[][]에 1을 채움
board를 순회하면서 dfs로 영역의 개수를 카운팅
코드
import java.util.*;
public class Main {
 static int m, n, K;
 static int[][] board;
 static boolean[][] visited;
 static int[] dx = {0, 0, 1, -1}; 
 static int[] dy = {1, -1, 0, 0};
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 m = scanner.nextInt();
 n = scanner.nextInt();
 K = scanner.nextInt();
 board = new int[m][n];
 visited = new boolean[m][n];
 for(int i = 0; i < K; i++){
 int startX = scanner.nextInt();
 int startY = scanner.nextInt();
 int endX = scanner.nextInt();
 int endY = scanner.nextInt();
 for(int j = startY; j < endY; j++){
 for(int l = startX; l < endX; l++){
 board[j][l] = 1;
 }
 }
 }
 List<Integer> answer = new ArrayList<>();
 for(int i = 0; i < m; i++){
 for(int j = 0; j < n; j++){
 if(board[i][j] == 0 && !visited[i][j]){
 answer.add(dfs(i, j));
 }
 }
 }
 Collections.sort(answer);
 System.out.println(answer.size());
 for (int area : answer) {
 System.out.print(area + " ");
 }
 }
 private static int dfs(int x, int y) {
 visited[x][y] = true;
 int area = 1;
 for(int i = 0; i < 4; i++){
 int nx = x + dx[i];
 int ny = y + dy[i];
 if(nx >= 0 && ny >= 0 && nx < m && ny < n && board[nx][ny] == 0 && !visited[nx][ny]){
 area += dfs(nx, ny);
 }
 }
 return area;
 }
}
정리
왜 모눈종이를 뒤집었지..? 찾느라 한참 걸림.. 뭔가 문제 해석이 더 어려움..
수능 문제 같음

99클럽 코테 스터디 34일차 - dfs

댓글